题解：CF2033F Kosuke's Sloth

原题链接

• 洛谷 CF2033F Kosuke's Sloth

参考资料

• 皮萨诺周期 - 维基百科
• A000045 - OEIS

题意简述

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

解题思路

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

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

参考代码

 #include <bits/stdc++.h>
using namespace std;
 
using ll=long long;
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;
		}
		int f1=1,f2=1,f3=1;
		ll cnt=2;
	    while(f3!=0)
	    {
	    	f3=(f1+f2)%k;
	    	f1=f2;
	    	f2=f3;
	    	cnt++;
	    }
	    cout<<cnt*n%mod<<'\n';
	}
	return 0;
}