相关链接
题目传送门: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; }