BZOJ4666: 小Z的胡话【斐波那契循环节】

题目描述：

题目分析：

对于一个longlong级别的斐波那契数列我们能做什么呢？ naive一点就只能算一算模mod下的第n项了。 如果这个mod很小，那么我们暴力枚举就可以得到答案。 如果x%Mod=a%Mod, 那么对于一个比Mod小的mod，x%mod也一定等于a%mod 也就是说我们可以先取一个小mod，把x%mod=a%mod的x找出来放进vector里面，再考虑大Mod的情况。 但是x显然有无穷个，于是我们打一打表会惊讶然后恍然大悟斐波那契数列模一个数是有周期的。 于是我们只需要把第一个周期中的x找出来，为了方便，我们让mod每次乘10，新mod下的x一定是原mod下的x+几倍周期得到的，同样我们只需要找新mod的第一个周期内的x

mod p^k的周期按道理来说应该是mod p周期的整数倍，打表也可以验证，所以判断是否达到新周期只需要不断地往后推上一次的周期，判断是否回到原点即可。

一轮的复杂度就是$O(cnt\ast T_{mod\ast 10}/T_{mod})$，cnt是很少的，而$T_{mod}$大约是mod的1.5倍，所以是很快的。

至于斐波那契为什么有周期可以参考这篇论文（然而我看不下去。。 ），网上也有很多关于循环节的题目。

Code：

#include<bits/stdc++.h> #define LL long long using namespace std; LL mod,a,L,L2; struct Mat{ LL s[2][2]; Mat(){memset(s,0,sizeof s);} void init(LL k){ s[0][0]=1,s[0][1]=0,s[1][0]=0,s[1][1]=1; Mat b;b.s[0][0]=0,b.s[0][1]=b.s[1][0]=b.s[1][1]=1; for(;k;k>>=1,b=b*b) if(k&1) *this=*this*b; } /*u64 Mul(u64 a,u64 b) { if (mod<=1000000000) return a*b%mod; return b?((Mul(a,b>>16)<<16)+a*(b&65535))%mod:0; }*/ inline LL mul(LL a,LL b){return (a*b-(long long)((long double)a*b/mod)*mod+mod)%mod;} inline void add(LL &x,LL y){x+=y+(x+y>=mod?-mod:0);} Mat operator * (const Mat &B){ Mat ret; for(int k=0;k<2;k++) for(int i=0;i<2;i++) if(s[i][k]) for(int j=0;j<2;j++) if(B.s[k][j]) add(ret.s[i][j],mul(s[i][k],B.s[k][j])); return ret; } }f,g,t; vector<LL>ans,ans2; int main() { cin>>a; ans.push_back(0),mod=L=1; for(int p=1;p<=13;p++){ mod*=10,L2=0; g.init(L),f.init(0); do{ for(LL i:ans){ t.init(i+L2); if(t.s[1][0]==a%mod) ans2.push_back(i+L2); } f=f*g,L2+=L; }while(f.s[0][0]!=1||f.s[0][1]!=0||f.s[1][0]!=0||f.s[1][1]!=1); L=L2,ans.swap(ans2),ans2.clear(); } if(ans.empty()) puts("-1"); else cout<<ans[0]<<endl; }