这类型的题目其实没什么意思..知道怎么做后，就有固定套路了..而且感觉这东西要出的很难的话，有这种方法解常数会比较大吧..所以一般最多套一些比较简单的直接可以暴力求循环节的题目了..
/** @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 <bits/stdc++.h>
#define LL long long
#define PII pair<int ,int>
#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
", ++icas, ans);
}
return 0;
}