跳跃(处理操作迭代-等价替代)
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;}