参考资料

• Pisano period - Wikipedia
• A000045 - OEIS

题意简述

求 Fibonacci 数列中第 $n$ 个能被 $k$ 整除的数的下标。

解题思路

Fibonacci 数列对 $k$ 取模具有周期性（皮萨诺周期），且周期 $r\le 6k$。

暴力枚举求出周期 $r$，则第 $n$ 个数的下标为 $rn$。

参考代码

402 Bcpp

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int mod=1e9+7;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		ll n,k;
		cin>>n>>k;
		n%=mod;
		if(k==1)
		{
			cout<<n<<'\n';
			continue;
		}
		ll f1=1,f2=1,f3=1,cnt=2;
		while(f3!=0)
		{
			f3=(f1+f2)%k;
			f1=f2;
			f2=f3;
			cnt++;
		}
		cout<<cnt*n%mod<<'\n';
	}
	return 0;
}