跳跃(处理操作迭代-等价替代)

Problem2 跳跃(jump.cpp/c/pas)

【题目描述】

一开始你位于数轴上的x位置,一次跳跃你可以从x跳跃到(9x+4)mod 1000000007或者(27x+13)mod 1000000007。求跳回到原点的最少跳跃次数。

保证通过有限次跳跃可以回到原点。

【输入格式】

一行一个整数x表示你的初始坐标,保证0<=x<1000000007

【输出格式】

一行一个整数表示最小的跳跃次数。

【样例输入】

555555559

【样例输出】

1

【数据范围】

对于40%的数据,答案<=20

对于100%的数据,答案<=100000

神结论:

9x+4等价于2次3x+1

27x+13等价于3次3x+1

#include<cstdio>

include<iostream>

include<functional>

include<algorithm>

include<cstring>

include<cstdlib>

using namespace std;

define MAXN (100000)

define F (1000000007)

long long x; int main() { freopen("jump.in","r",stdin); freopen("jump.out","w",stdout); while (scanf("%d",&x)==1) { int ans=0; for (;!((!x)&&ans!=1);x=(3*x+1)%F) ans++; printf("%d\n",ans/3+bool(ans%3));
} return 0; }