题解：CF2033F Kosuke's Sloth

· · 题解

参考资料

题意简述

求 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;
        }
        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;
}