这类型的题目其实没什么意思..知道怎么做后，就有固定套路了..而且感觉这东西要出的很难的话，有这种方法解常数会比较大吧..所以一般最多套一些比较简单的直接可以暴力求循环节的题目了..
/** @Date : 2017-09-26 16:37:05 * @FileName: HDU 3977 斐波那契循环节.cpp * @Platform: Windows * @Author : Lweleth (SoungEarlf@gmail.com) * @Link : https://github.com/ * @Version : $Id$ */#include#define LL long long#define PII pair #define MP(x, y) make_pair((x),(y))#define fi first#define se second#define PB(x) push_back((x))#define MMG(x) memset((x), -1,sizeof(x))#define MMF(x) memset((x),0,sizeof(x))#define MMI(x) memset((x), INF, sizeof(x))using namespace std;const int INF = 0x3f3f3f3f;const double eps = 1e-8;/LL mul(LL x, LL y, LL mod){ return (x * y - (LL)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;}struct Matrix{ LL m[2][2];};Matrix A;Matrix I = {1, 0, 0, 1};Matrix multi(Matrix a, Matrix b, LL MOD){ Matrix c; for(int i = 0; i < 2; i++) { for(int j = 0; j < 2; j++) { c.m[i][j] = 0; for(int k = 0; k < 2; k++) c.m[i][j] = (c.m[i][j] % MOD + (a.m[i][k] % MOD) * (b.m[k][j] % MOD) % MOD) % MOD; c.m[i][j] %= MOD; } } return c;}Matrix power(Matrix a, LL k, LL MOD){ Matrix ans = I, p = a; while(k) { if(k & 1) { ans = multi(ans, p, MOD); k--; } k >>= 1; p = multi(p, p, MOD); } return ans;}LL gcd(LL a, LL b){ return b ? gcd(b, a % b) : a;}const int N = 400005;const int NN = 5005;LL num[NN], pri[NN];LL fac[NN];int cnt, c;bool prime[N];int p[N];int k;void isprime(){ k = 0; memset(prime, true, sizeof(prime)); for(int i = 2; i < N; i++) { if(prime[i]) { p[k++] = i; for(int j = i + i; j < N; j += i) prime[j] = false; } }}LL fpow(LL a, LL b, LL m){ LL ans = 1; a %= m; while(b) { if(b & 1) { ans = mul(ans, a , m); b--; } b >>= 1; a = mul(a , a , m); } return ans;}LL legendre(LL a, LL p){ if(fpow(a, (p - 1) >> 1, p) == 1) return 1; else return -1;}void Solve(LL n, LL pri[], LL num[]){ cnt = 0; LL t = (LL)sqrt(1.0 * n); for(int i = 0; p[i] <= t; i++) { if(n % p[i] == 0) { int a = 0; pri[cnt] = p[i]; while(n % p[i] == 0) { a++; n /= p[i]; } num[cnt] = a; cnt++; } } if(n > 1) { pri[cnt] = n; num[cnt] = 1; cnt++; }}void Work(LL n){ c = 0; LL t = (LL)sqrt(1.0 * n); for(int i = 1; i <= t; i++) { if(n % i == 0) { if(i * i == n) fac[c++] = i; else { fac[c++] = i; fac[c++] = n / i; } } }}LL get_loop(LL n){ Solve(n, pri, num); LL ans = 1; for(int i = 0; i < cnt; i++) { LL record = 1; if(pri[i] == 2) record = 3; else if(pri[i] == 3) record = 8; else if(pri[i] == 5) record = 20; else { if(legendre(5, pri[i]) == 1) Work(pri[i] - 1); else Work(2 * (pri[i] + 1)); sort(fac, fac + c); for(int k = 0; k < c; k++) { Matrix a = power(A, fac[k] - 1, pri[i]); LL x = (a.m[0][0] % pri[i] + a.m[0][1] % pri[i]) % pri[i]; LL y = (a.m[1][0] % pri[i] + a.m[1][1] % pri[i]) % pri[i]; if(x == 1 && y == 0) { record = fac[k]; break; } } } for(int k = 1; k < num[i]; k++) record *= pri[i]; ans = ans / gcd(ans, record) * record; } return ans;}LL fib[5005];void Init(){ A.m[0][0] = 1; A.m[0][1] = 1; A.m[1][0] = 1; A.m[1][1] = 0; fib[0] = 0; fib[1] = 1; for(int i = 2; i < 5005; i++) fib[i] = fib[i - 1] + fib[i - 2];}//int main(){ Init(); isprime(); int T; cin >> T; int icas = 0; while(T--) { LL n; cin >> n; LL ans = get_loop(n); printf("Case #%d: %lld\n", ++icas, ans); } return 0;}