题解 P7325 【[WC2021] 斐波那契】

· · 题解

题意

我们定义F_0=a,F_1=b,F_n=F_{n-1}+F_{n-2}\pmod m

现在给定 n 组询问，对于每组询问请找到一个最小的整数 p，使得 F_p=0。

题解

在 \rm LOJ 上看到一个超级优美的方法，来记录一下，希望想出来的人不要打我QwQ

一开始的过程伪掉了，关键步骤重写了一下

\begin{cases} F_0&=a,\\ F_1&=b,\\ F_n&=F_{n-1}+F_{n-2} \end{cases} \Longrightarrow \begin{cases} fib_0&=0,\\ fib_1&=1,\\ F_n&=bfib_{i}+afib_{i-1} \end{cases}

记 (a,b)F_n 为 F_0=a,F_1=b 的斐波那契数列的第 n 项

(a,b)F_n\equiv0\pmod m\Longleftrightarrow (\frac{a}{\gcd(a,b,m)},\frac{b}{\gcd(a,b,m)})F_n\equiv0 \pmod{\frac{m}{\gcd(a,b,m)}}

记 \frac{a}{\gcd(a,b,m)},\frac{b}{\gcd(a,b,m)},\frac{m}{\gcd(a,b,m)} 分别为 a^\prime,b^\prime,m^\prime 。对于每个 m^\prime 分别处理。不难发现不同m^\prime 的数量上界为 2\times\sqrt{m} 而且几乎不可能卡满。 (打了个表只有128)

\begin{aligned} &a^\prime fib_{i-1}+b^\prime fib_i\equiv 0\pmod {m^\prime}\\ &a^\prime fib_{i-1}\equiv(m^\prime-b^\prime) fib_i\pmod {m^\prime} \end{aligned}

首先有 a|m\Rightarrow a|(ba\bmod m)

感性理解为若一个数是模数的因数，那么其若干倍在膜 m 下仍是其的倍数。

考虑 a' fib_{i-1}\equiv (m'-b') fib_i\pmod {m'}

(\gcd(a',m'-b',m')=1,\gcd(fib_i,fib_{i-1})=1)

$(m'-b')fib_i\bmod m'$ 是 $\gcd(m'-b',m')$、$\gcd(fib_i,m')$ 的倍数 由于相等： $(m'-b')fib_i\bmod m'$ 是 $\gcd(a',m')$ 、$\gcd(fib_{i-1},m')$ 的倍数 $a'fib_{i-1}\bmod m'$ 是 $\gcd(m'-b',m')$、$\gcd(fib_i,m')$ 的倍数 $$ \begin{cases} \gcd(a',m')|(m'-b')fib_i\\ \gcd(fib_i,m')|a'fib_{i-1} \end{cases} $$ 由于 $\gcd(a',m')\perp (m'-b')$ 且 $\gcd(fib_i,m')\perp fib_{i-1}$ ，有： $$\begin{cases}\gcd(a',m')|fib_i\\ \gcd(fib_i,m')|a'\end{cases} \Rightarrow \begin{cases}\gcd(a',m')|\gcd(fib_i,m')\\ \gcd(fib_i,m')|\gcd(a',m')\end{cases}$$ 因而得证 $\gcd(a',m')=\gcd(fib_i,m')$。同理易得 $\gcd(b',m')=\gcd(fib_{i-1},m')

所以有：

\begin{cases} \gcd(a^\prime,m^\prime)=\gcd(fib_i,m^\prime)\\ \gcd(fib_{i-1},m^\prime)=\gcd(m^\prime-b^\prime,m^\prime)\\ \frac{a^\prime}{\gcd(a^\prime,m^\prime)}\frac{fib_{i-1}}{\gcd(fib_{i-1},m^\prime)}\equiv\frac{m^\prime-b^\prime}{\gcd(m^\prime-b^\prime,m^\prime)}\frac{fib_i}{\gcd(fib_i,m^\prime)} \color{black}\pmod {\frac{m^\prime}{\gcd(a^\prime,m^\prime)\gcd(fib_{i-1},m^\prime))}} \end{cases}

最后一个柿子可以写成分式，记从左至右依次为 a^{\prime\prime},fib_{i-1}^\prime,b^{\prime\prime},fib_i^\prime,m^{\prime\prime}，则有：

\frac{a^{\prime\prime}}{b^{\prime\prime}}\equiv \frac{fib_i^{\prime}}{fib_{i-1}^\prime}\pmod {m^{\prime\prime}}

两侧都只与自己有关，并且都在模下有意义。可以压成一个三元组，用 map 查询即可

代码

#include<bits/stdc++.h>
using namespace std;
void exgcd(int a,int b,int &x,int &y){
    if(!b)x=1,y=0;
    else{
        exgcd(b,a%b,x,y);
        int t=x;x=y;
        y=t-a/b*y;
    }
}
int inv(int a,int b){
    int x,y;exgcd(a,b,x,y);
    return (x%b+b)%b;
}
const int N=6e5+10;
int n,m;int ans[N];
struct node{int a,b,id;node(int _a,int _b,int _id):a(_a),b(_b),id(_id){}};
vector<node>Q[N];
signed main(){
    scanf("%d%d",&n,&m);
    for(int i=1,A,B;i<=n;i++){
        scanf("%d%d",&A,&B);
        if(A==0)ans[i]=0;
        else if(B==0)ans[i]=1;
        else{
            int k=__gcd(A,__gcd(B,m));
            Q[m/k].push_back(node(A/k,B/k,i));ans[i]=-1;
        }
    }
    for(int i=2;i<=m;i++)if(Q[i].size()){
        auto work=[&](int a,int b){
            int m1=__gcd(a,i),m2=__gcd(b,i),m3=i/m1/m2;
            return make_pair(make_pair(m1,m2),1ll*(a/m1)*inv(b/m2,m3)%m3);
        };
        static int f[N],len;f[0]=0,f[1]=1;
        for(len=2;len<=6*i;len++){
            f[len]=(f[len-1]+f[len-2])%i;
            if(!f[len])break;
        }
        map<pair<pair<int,int>,int>,int>mp;
        for(int j=1;j<=len;j++){
            auto tmp=work(f[j],f[j-1]);
            if(mp.find(tmp)==mp.end())
                mp[tmp]=j;
        }
        for(auto q:Q[i]){
            auto tmp=work(q.a,i-q.b);
            if(mp[tmp]>=2)
                ans[q.id]=mp[tmp];
        }
    }
    for(int i=1;i<=n;i++)
        printf("%d\n",ans[i]);
}