题意
给出一个数,你要对他反复平方,平方完之后总是取运算结果的前n个十进制位(如果结果大于n位)作为答案,然后对这个答案继续进行刚才的操作。
这是一个循环的过程,你要找出在这个循环节中最大的数。
思路
首先是循环节这一点,意识到形成循环节并不难。从理论上来证明:我们可以设定一个运算#表示相乘取前n位这一操作,初始值为a,a#1=a,1为单位元,N为所有k及k位以下整数组成的集合,两个数做运算得到的结果必然属于N,则<N,#>构成一个有限群,<a^x>必然构成循环群。
取前n位这一操作可以用字符串流,但是那样常数非常大,所以还是考虑利用数学运算来实现,这样会提高速度。
找出循环节的方法有两种,一种是开一个set,算一次insert一次,如果碰到算过的就停下。还有一种是Floyd判圈法,也就是同时维护两个数A和B,每一次令A=A^2,B=B^3,也就是B总是会比A多走一步,这样如果有环,A和B一定会相遇,在相遇时停下。
代码
Floyd判圈法,数学方法求前n位。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> #include <complex> using namespace std; long long n; long long k; void nxt(long long &cur){ cur = cur * cur; int cnt = 0; long long nxt = 0; long long fac = 1; for(int i = 1; i <= n && cur; i++){ nxt += (cur%10)*fac; fac *= 10; cur /= 10; } fac /= 10; while(cur){ nxt /= 10; nxt += (cur%10)*fac; cur /= 10; } cur = nxt; } int main(){ int caseCnt; scanf(" %d",&caseCnt); for(int d = 1; d <= caseCnt; d++){ scanf(" %lld %lld",&n,&k); long long res = k; long long cura = k,curb = k; do{ nxt(cura); nxt(curb); res = max(res,curb); nxt(curb); res = max(res,curb); }while(cura != curb); printf("%lld\n",res); } } |