そんな法則知らなかった…。
https://csacademy.com/contest/round-59/task/fibonacci-mod/
問題
フィボナッチ数列f(0)=0, f(1)=1, f(N+2)=f(N)+f(N+1)について考える。
整数A,B,Mが与えられたとき、f(N) % M = A かつf(N+1) % M = Bを満たすNが存在すれば、その最小値を求めよ。
解法
試してみると、f(N) % Mの周期はMより大きいためO(M)かかる解法は取れない。
f(N+2)がf(N)とf(N+1)の2値からなることから、最悪ケースで一見周期が最大O(M^2)となりそうだが、実は6M以下になるらしい。
Pisano period - Wikipedia
フィボナッチ数を求めるのは行列累乗で解けるので、この問題は下記の通り行列に対する離散対数問題となる。
離散対数問題なのでこの問題はBaby-Step Giant-Stepの要領で解ける。
周期が最大6M≦10^10なので、(10^5)step程度繰り返せばよい。
int T; int A,B,M; const int MAT=2; struct Mat { ll v[MAT][MAT]; }; ll mo; Mat mulmat(Mat& a,Mat& b,int n=MAT) { ll mo2=4*mo*mo; int x,y,z; Mat r; FOR(x,n) FOR(y,n) r.v[x][y]=0; FOR(x,n) FOR(z,n) FOR(y,n) { r.v[x][y] += a.v[x][z]*b.v[z][y]; if(r.v[x][y]>mo2) r.v[x][y] -= mo2; } FOR(x,n) FOR(y,n) r.v[x][y]%=mo; return r; } void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>M>>A>>B; mo=M; Mat nex={.v={{0,1},{1,1}}}; Mat pre={.v={{M-1,1},{1,0}}}; Mat E={.v={{1,0},{0,1}}}; Mat preS=E,preS2=E; FOR(i,100000) { preS=mulmat(preS,pre); } map<pair<int,int>,ll> mp; FOR(i,100000) { int a=(preS2.v[0][0]*A+preS2.v[1][0]*B)%M; int b=(preS2.v[0][1]*A+preS2.v[1][1]*B)%M; if(mp.count({a,b})==0) mp[{a,b}]=100000LL*i; preS2=mulmat(preS2,preS); } ll mi=1LL<<60; FOR(i,100000) { int a=(E.v[0][0]*0+E.v[1][0]*1)%M; int b=(E.v[0][1]*0+E.v[1][1]*1)%M; if(mp.count({a,b})) { mi=min(mi,(i+mp[{a,b}])); } E=mulmat(E,nex); } if(mi==1LL<<60) mi=-1; cout<<mi<<endl; } }
まとめ
BSGS自体は思い浮かんだものの、Pisano Periodを知らなかったので「周期が最悪O(M^2)ありそうだし、BSGSもO(M logM)かかってダメだなー」とあきらめてしまっていた。