WC2021 斐波那契

题意

给定$p$.

$q$ 次询问，给定 $a,b$ ，定义 $f_0=a,f_1=b,f_i=f_{i-1}+f_{i-2}$ ，求 $f_i\mod p=0$ 的最小整数解 $i$

$p,q 10^5$ ($p$不一定是质数)

首先我们知道，第一次出现循环节的位置是$O(p)$的。

对于一个询问 $a,b$ ， 若 $\gcd(w,p)=1$ 则 $a,b$ 和 $aw,bw$ 等价。(显然第二个答案$\leq$第一个答案，然后由 $\gcd(x,p)=1$ 可得存在 $w^{-1} \bmod p$ )。 我们希望有一个 $x$ 能使得 $a$ 形式简单

如果 $p$ 是质数， $x=a^{-1} (\gcd(a,p)\not=1)$ 显然可行，那就可以转 $1,\frac{b}{a}$。 (否则write(1))

对于一个 $a$ ，我们可以 $\sum_{d|p}d = O(p\log \log p)$ 算出所有的 $a$ 答案，大概思路是遍历每个 $i$，然后知道可能的 $a$ 满足 $a\bmod q=r (q|p)$，然后最后从小到大遍历 $d$，显然可以由 $\bmod d$ 的答案转移到 $\bmod dx$ (当然要合并取min), $x$ 取 $d$外的最小因子即可(复杂度分析可能有点锅

然后 $a$ 不是质数的情况下，我们希望 $ax\bmod p=\gcd(a,p)$ ，直观想法大概是 exgcd(a,p) 得到 $x$。但这过不了大样例，为什么呢？因为 $\gcd(x,\frac{p,d})=1$ 但 $\gcd(x,p)$ 不一定 $=1$ ($d=\gcd(a,p)$)。

那有一个直观想法是 把 $x$ 里所有 $p$ 因子全删了，发现没有这个 $ax\bmod p$ 就重算，实测随机数据正确率 $\geq 99\%$ ，最终数据下80分(

然后有一个看上去靠谱的做法是，while(gcd(x,p)!=1) x+=p/d。 显然 $x\leftarrow x+\frac{p}{d}$ 对 $a$ 不会产生影响，只会对 $b$ 产生影响。

然后看上去跑的次数不是很多(

对于每个 $a$ 预处理 $x$ 没找到跑不过的数据(

如果有这一部分复杂度的证明或者hack欢迎来教育我，非常感谢

#include<bits/stdc++.h>
#include<tr1/unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
tr1::unordered_map<ll,bool> st;
const int inf=0x3f3f3f3f;
int fib[1000005];
bool chkmax(int &a,int b){return a<b?a=b,1:0;}
bool chkmin(int &a,int b){return a>b?a=b,1:0;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
void exgcd(int a,int b,int &x,int &y){
    if(!b){x=1,y=0;return;}
    exgcd(b,a%b,y,x);
    y-=(a/b)*x;
}
int lf[100000005],*at=lf;
int *newI(int x){int *ret=at;at+=x;return ret;}
int *f[100005];
int g[129][100005];
int nex[129];
int d[129],is[100005];
int q,p,m,c;
int ix[1000005],id[1000005];
void init(int a,int &x,int &d){
    int y;
    exgcd(a,p,x,y);
    d=gcd(a,p);
    if(x<0)x+=p/d;
}
void chk(int a,int b,int id){
    int x=ix[a];
    int d=::id[a];
    if(b)b=p-b;
    if(b%d)return;
    //if(x<0)x+=p/d;
    x=(ll)x*(b/d)%p;
    int w=p/d;
    chkmin(g[is[w]][x%w],id);
}
void solve(int w){
    for(int i=1;i<=m;++i)for(int j=0;j<d[i];++j)g[i][j]=inf;
    for(int i=1;i<=c;++i){
        chk(i-1,(ll)fib[i]*w%p,i);
    }
    for(int i=1;i<m;++i){
        int v=nex[i];
        for(int j=0;j<d[v];++j)chkmin(g[v][j],g[i][j%d[i]]);
    }
    for(int i=0;i<p;++i)f[is[w]][i]=g[m][i];
}
int val[100005];
int main(){
    #define make(x,y) ((ll)x*p+y)
    scanf("%d%d",&q,&p);
    if(p==1){
        for(;q;--q)printf("0\n");
        return 0;
    }
    fib[0]=fib[1]=1;
    st[make(1,1)]=1;
    for(int i=2;;++i){
        fib[i]=fib[i-1]+fib[i-2];
        if(fib[i]>=p)fib[i]-=p;
        ll w=make(fib[i-1],fib[i]);
        if(st[w]){c=i;break;}
        st[w]=1;
    }
    for(int i=0;i<c;++i){
        init(fib[i],ix[i],id[i]);
    }
    for(int i=1;i<=p;++i)if(!(p%i)){
        d[is[i]=++m]=i;
        f[m]=newI(p);
    }
    for(int i=1;i<m;++i)for(int j=i+1;j<=m;++j)if(!(d[j]%d[i])){nex[i]=j;break;}
    for(int x=1;x<m;++x){
        solve(d[x]);
    }
    int xm=m;
    for(int a=1;a<=p;++a){
        int x,y,g;
        exgcd(a,p,x,y);
        g=gcd(a,p);
        if(x<0)x+=p;
        while(gcd(x,p)>1){x+=p/g;if(x>=p)x-=p;}
        val[a]=x;
    }
    for(;q;--q){
        int a,b;
        scanf("%d%d",&a,&b);
        (b-=a)<0?b+=p:0;
        int v=gcd(a,p);
        if(v==p){printf("0\n");continue;}

        b=(ll)b*val[a]%p;
        v=(ll)a*val[a]%p;
        //assert(v==g);
        assert(is[v]);
        //if(!is[v]){d[is[v]=++xm]=v;f[xm]=newI(p);solve(v);}
//        printf("%d\n",(ll)a*x%p);
//        printf("%d\n",x);
        printf("%d\n",f[is[v]][b]==inf?-1:f[is[v]][b]);
    }
    //printf("%d\n",xm);
    return 0;
}