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