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