相关链接
题目传送门：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1195
二次剩余相关：http://staff.ustc.edu.cn/~lvmin05/jssl/Chap3%20%B6%FE%B4%CE%CA%A3%D3%E0.ppt
二次剩余相关：http://pan.baidu.com/s/1geBDodH
神犇题解：http://blog.csdn.net/acdreamers/article/details/10983813
解题报告
我们分三步走：
- 将模数质因数分解
- 对于每一个$p_i^m$我们计算其循环节$l_i$
- 将所有$l_i$取$lcm$
显然第一步和第三步没有难度
我们考虑第二步，这里有一个神奇得结论：
若$G(p)$为Fibonacci数列在模素数$p$意义下的最短循环节
那么$\bmod p^m$的最短循环节为$G(p)\cdot p^{m-1}$
现在问题转化为求$G(p)$，这里又有一个神奇的结论：
若$5$为$p$的二次剩余，则$G(p)$为$p-1$的因子。否则为$2(p+1)$的因子
然后我们就可以通过从小到大枚举因数+$O(\log n)$判断的方法得到答案了
另外的话，这个算法似乎没有比较准确的复杂度。不过我们可以假装他是$O(\sqrt{n} \log n)$的
再另外的话，这份代码会$T$，但我又不想优化了，反正这个东西也不可能考 QwQ
Code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
class Fibonacci{
int ans[4],tra[4],MOD;
public:
inline bool cal(int t, int mod) {
ans[1] = tra[1] = tra[2] = tra[3] = 1;
ans[0] = ans[2] = ans[3] = tra[0] = 0; MOD = mod;
Pow(tra, tra, t - 2); Mul(ans, ans, tra);
return ans[1] == 1 && !ans[0];
}
private:
inline void Pow(int *ans, int *a, int t) {
static int ret[4],cur[4];
ret[0]=ret[3]=1; ret[1]=ret[2]=0;
memcpy(cur,a,sizeof(cur));
for (;t;t>>=1,Mul(cur,cur,cur))
if (t&1) Mul(ret,cur,ret);
memcpy(ans, ret, sizeof(ret));
}
inline void Mul(int *ans, int *a, int *b) {
static int ret[4];
ret[0] = ((ll)a[0] * b[0] + (ll)a[1] * b[2]) % MOD;
ret[1] = ((ll)a[0] * b[1] + (ll)a[1] * b[3]) % MOD;
ret[2] = ((ll)a[2] * b[0] + (ll)a[3] * b[2]) % MOD;
ret[3] = ((ll)a[2] * b[1] + (ll)a[3] * b[3]) % MOD;
memcpy(ans, ret, sizeof(ret));
}
}fib;
ll GCD(ll a, ll b) {
return b? GCD(b, a%b): a;
}
int Pow(int w, int t, int mod) {
int ret = 1;
for (;t;t>>=1,w=(ll)w*w%mod)
if (t&1) ret=(ll)ret*w%mod;
return ret;
}
inline ll G(ll p) {
if (p == 2) return 3;
else if (p == 3) return 8;
else if (p == 5) return 20;
static ll LIM = 0; stack<int> stk;
if (Pow(5, (p-1)/2, p) == 1) LIM = p - 1;
else LIM = p + 1 << 1;
for (int i=1;i*i<=LIM;i++) {
if (LIM % i == 0) {
if (fib.cal(i+2, p)) return i;
else stk.push(LIM / i);
}
}
for (int ret;!stk.empty();) {
ret = stk.top(); stk.pop();
if (fib.cal(ret+2, p)) return ret;
}
}
inline ll cal(int a, int b) {
static ll INF = 4e18, ret;
for (ret=G(a);b>1;b--) ret = ret * a;
return ret;
}
inline ll solve(int mod) {
static const int N = 1e5;
static int pri[N],cnt[N],tot;
if (mod == 1) return 1; tot = 0;
for (int i=2;i*i<=mod;i++) {
if (mod % i == 0) {
pri[++tot] = i; cnt[tot] = 0;
for (;mod%i==0;mod/=i) ++cnt[tot];
}
} if (mod>1) pri[++tot] = mod, cnt[tot]=1;
ll ret = 1;
for (int i=1,tmp;i<=tot;i++) {
tmp = cal(pri[i], cnt[i]);
ret = ret / GCD(ret, tmp) * tmp;
} return ret;
}
int main() {
for (int T=read();T;T--)
printf("%lld\n",solve(read()));
return 0;
}