[UVa 11549]Calculator Conundrum

danihao123 posted @ 2016年9月17日 14:49 in 题解 with tags UVa Floyd判圈 , 546 阅读
转载请注明出处:http://danihao123.is-programmer.com/

很有趣的一个题。

很明显,求出的结果一定会循环,形成一个环。然后呢?假如有一只乌龟和一只兔子在这个赛道上赛跑(同起点),兔子的速度是乌龟的两倍,那么最后兔子一定会“追上”乌龟,然后接下来的情况就是以前的循环了。

这种神奇的算法叫做Floyd判圈算法。话说还有一种Brent判圈算法……常数比它还要小。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
char buf[25];
int n;
inline ull next(ull x){
    register ull res=0;
    register int i,length;
    memset(buf,0,sizeof(buf));
    length=sprintf(buf,"%llu",x*x);
    length=min(length,n);
    for(i=0;i<length;i++){
        res=res*10+buf[i]-'0';
    }
    return res;
}
int main(){
    ull k1,k2,ans;
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%llu",&n,&k1);
        ans=k1;
        k2=k1;
        do{
            k1=next(k1);
            k2=next(k2);
            if(k2>ans)
                ans=k2;
            k2=next(k2);
            if(k2>ans)
                ans=k2;
        }while(k1!=k2);
        printf("%llu\n",ans);
    }
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter