kmjp's blog

競技プログラミング参加記です

CSAcademy Round #59 : E. Fibonacci Mod

そんな法則知らなかった…。
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

フィボナッチ数を求めるのは行列累乗で解けるので、この問題は下記の通り行列に対する離散対数問題となる。
 \displaystyle

\begin{bmatrix}
1&1\\
1&0
\end{bmatrix}^N
\begin{bmatrix}
f(1)\\
f(0)
\end{bmatrix}
=
\begin{bmatrix}
B\\A
\end{bmatrix}

離散対数問題なのでこの問題は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)かかってダメだなー」とあきらめてしまっていた。