题解：CF2033F Kosuke's Sloth

_YFS_ · 2025-01-10 22:52:36 · 题解

数学题。

题意

定义 G(n,k) 为第 n 个能被 k 整除的斐波那契数的下标。给定 n 和 k，计算 G(n,k)。

多测，结果对 10^9+7 取模。

例如：G(3,2)=9，因为第 3 个能被 2 整除的斐波那契数是 34，即 [1,1,\textbf{2},3,5,\textbf{8},13,21,\textbf{34}]。

前置芝士

皮萨诺周期：斐波那契数列取模 k 具有周期性，这个周期叫做皮萨诺周期，也就是 G(n,k)=n\times G(1,k)，并且模 k 的循环节长度 \le6k。

证明略。还不是因为不会

思路

暴力枚举出倍数，乘上 n 即可。

代码

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
int main()
{
    int t,k;
    long long n;
    cin>>t;
    while(t--)
    {
        cin>>n>>k;
        if(k==1) cout<<n%mod<<'\n';//特判 
        else
        {
            int a1,a2,a3=0,ans=0;
            a1=a2=1;//斐波那契数列初始化f(1)=f(2)=1 
            for(int i=3;;i++)//暴力枚举找出倍数 
            { 
                a3=(a1+a2)%k;
                if(!a3)
                {
                    ans=i;
                    break;
                }
                a1=a2;
                a2=a3;
            }
            cout<<n%mod*ans%mod<<'\n';//取模+输出 
        }
    }
    return 0;
}