https://wenku.baidu.com/view/7fc328eb4693daef5ef73d87.html 先上文献资料 这里面提到了几个性质 1.对于和5互质的质数p，如果5是 mod p的二次剩余，那在 mod p 意义下的循环节长度为(p-1)的因子 2.对于和5互质的质数p ，如果5是 mod p 的非二次剩余，那么在 mod p 意义下的循环节长度为(2p+2)的因子 3.对于模 形如 p^k 意义下的循环节，循环节的长度为 mod p意义下的循环节长度 * p^(k-1) 4. 对于模形如 n=p1^k1+p2^k2+...... 循环节的长度为每个p^k对应的循环节长度的lcm 对于比5小的数，直接枚举就行 hdu-4794 https://vjudge.net/problem/HDU-4794 坐标的变换规律符合，斐波拉契循环节 因为是坐标变换，和数列不太一样 (1,2,3) : (x1,x2)->(x3,x1)->(x2,x3)->(x1,x2)奇数的话就为这个数因为奇数必须要经历两次循环才能返回原来的(x1,x2) (1,2,3,4) : (x1,x2)->(x3,x4)->(x1,x2)偶数的话就为这个数/2 #include #define rep(i,a,b) for(int i=(a);i<(b);++i) #define rrep(i,b,a) for(int i = (b); i >= (a); --i) #define clr(a,x) memset(a,(x),sizeof(a)) #define LL unsigned long long using namespace std; LL n; LL gcd(LL a, LL b) { while (a && b) { if (a > b) a %= b; else b %= a; } return a + b; } LL lcm(LL a,LL b) { return a * b / gcd(a,b); } void mul(LL A[2][2],LL B[2][2],LL ret[2][2],LL mod) { LL C[2][2] = { 0 }; rep(i,0,2) rep(j,0,2) rep(k,0,2) C[i][j] = (C[i][j] + A[i][k] * B[k][j] % mod) % mod; rep(i,0,2) rep(j,0,2) ret[i][j] = C[i][j]; } void qpow(LL base[2][2],LL p,LL dest[2][2],LL mod) { LL ret[2][2] = { 0 }; ret[0][0] = ret[1][1] = 1; while (p > 0) { if (p & 1) mul(ret,base,ret,mod); mul(base,base,base,mod); p >>= 1; } rep(i,0,2) rep(j,0,2) dest[i][j] = ret[i][j]; } LL qpow(LL base,LL p,LL mod) { LL ret = 1; while (p) { if (p & 1) ret = ret * base % mod; base = base * base % mod; p >>= 1; } return ret; } LL S[10000],c; LL f1,f2; void F(LL p,LL mod)// { LL A[2][2] = { 0 }; A[0][0] = 1; A[0][1] = 1; A[1][0] = 1; A[1][1] = 0; qpow(A,p-1,A,mod);//A的p-1次幂 （mod p） f1 = (A[1][0]+A[1][1]) % mod; f2 = (A[0][0] + A[0][1]) % mod; } LL loop(LL mod) { if (mod == 2) return 3; else if (mod == 3) return 8; else if (mod == 5) return 20; LL p; //判断5是不是该质数的二次剩余，套用性质1 2 if (qpow(5,(mod-1)>>1,mod) == 1) { p = mod - 1; } else { p = 2*(mod + 1); }//先框定p的范围 c = 0; for(LL i = 1; i * i <= p; ++i)//枚举的是循环节的长度，如果i为循环节的长度，那么第i个数和第i+1个数必定为0，1 { if (p % i == 0) { LL x = i , y = p / i; F(x,mod);//计算在mod i 意义下的fib数列 if (f1 == 0 && f2 == 1) { return x; } if (y != x) S[c++] = y; } } while (c > 0)//枚举另一半 { F(S[--c],mod); if (f1 == 0 && f2 == 1) return S[c]; } return 0; } int main() { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); // cout << qpow(5,(mod - 1)/2,mod) << endl; while (cin >> n) { LL x = n; LL ans = 1; for(LL i = 2; i * i <= x; ++i)//性质4，先唯一分解x { if (x % i == 0) { LL c=1; LL len = loop(i); while(x%i==0) { x/=i; c*=i; } c/=i; LL temp=c*len; ans=lcm(ans,temp); } } if (x > 1) { LL len = loop(x); ans = lcm(ans,len); } if (ans % 2 == 0) ans /= 2; cout<