Description
众所周知，小葱同学擅长计算，尤其擅长计算组合数。但是对组合数有了充分研究的小葱同学对组合数失去了兴趣，而开始研究数列。
我们定义$F_0=a,F_1=b,F_i=(F_{i-1}+F_{i-2})mod m (i leq 2)$
现在给定 $n$ 组询问，对于每组询问请找到一个最小的整数 $p$，使得 $F_p = 0$。
Solution
可以通过打表找规律发现$F_n=bf_n+af_{n-1}$
设$d=gcd (a,b,m)$
$$bf_n+af_{n-1}equiv 0pmod miff frac{b}{d}f_n+frac{a}{d}f_{n-1}equiv 0 pmod{frac{m}{d}}$$
令$a^primeleftarrow frac{a}{d},b^primeleftarrow frac{b}{d},m^primeleftarrowfrac{m}{d}，q=gcd(a',m'),p=gcd(b',m'), q'=gcd(f_n,m'), p'=gcd(f_{n-1},m')$
且因为 $gcd(a^prime,b^prime,m^prime)=1,gcd(f_n,f_{n-1},m')=1$，所以 $gcd(p,q)=1,gcd(p',q')=1$。
于是有
egin{cases}pmid b'f_n+a'f_{n-1}\qmid b'f_n+a'f_{n-1}\p'mid b'f_n+a'f_{n-1}\q'mid b'f_n+a'f_{n-1}end{cases}
考虑 $egin{cases}q|b'f_n+a'f_{n-1}\q'|b'f_n+a'f_{n-1}end{cases}$
因为$q mid b'$或$q=1$，$q' mid f_{n-1}$或$q'=1$
所以 $egin{cases}qmid f_n\q'mid aend{cases}$
egin{cases}qmid f_n\q'mid aend{cases} egin{cases}qmidgcd(f_n,m')\q'mid gcd(a',m')end{cases} egin{cases}gcd(a',m')mid gcd(f_n,m')\ gcd(f_n,m')mid gcd(a',m')end{cases} $$gcd(a',m')=gcd(f_n,m')$$
同理可证： $gcd(f_{n-1},m')=gcd(b',m')$。
egin{aligned}
&b'f_n+a'f_{n-1}equiv 0pmod {m'}\
Rightarrow & frac{b'}{p}frac{f_n}{q}+frac{a'}{q}frac{f_{n-1}}{p}equiv 0pmod{frac{m'}{pq}}\
Rightarrow & frac{f_n/q}{f_{n-1}/p}equiv -frac{a'/q}{b'/p} pmod{frac{m'}{pq}}
end{aligned}
所以枚举$m$的所有因数，在map中保存所有的$left(p,q,frac{f_n/q}{f_{n-1}/p}mod frac{m'}{pq} ight)$，求答案时查表
#include<iostream> #include<vector> #include<cstdio> #include<map> using namespace std; int ans[100005]; long long n,m,f[200005]={0,1}; struct Ele{ long long a,b,c; bool operator < (const Ele &z)const{ if(a!=z.a)return a<z.a; if(b!=z.b)return b<z.b; return c<z.c; } }; vector<Ele>ve[100005]; map<Ele,int>mp; inline int read(){ int w=0,f=1; char ch=0; while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=getchar(); return w*f; } long long gcd(long long a,long long b){return b?gcd(b,a%b):a;} void exgcd(long long a,long long b,long long &x,long long &y){ if(!b){x=1,y=0;return;} exgcd(b,a%b,x,y); int t=x; x=y,y=t-a/b*y; } long long inv(long long a,long long p){ long long x=0,y=0; exgcd(a,p,x,y); return (x%p+p)%p; } Ele calc(long long a,long long b,long long p){ long long d1=gcd(a,p),d2=gcd(b,p),pp=p/d1/d2; return (Ele){d1,d2,(a/d1)*inv(b/d2,pp)%pp}; } int main(){ n=read(),m=read(); for(int i=1;i<=n;i++){ int a=read(),b=read(); if(!a)ans[i]=0; else if(!b)ans[i]=1; else{ long long temp=gcd(a,gcd(b,m)); ve[m/temp].push_back((Ele){a/temp,b/temp,i}),ans[i]=-1; } } for(long long i=2;i<=m;i++)if(ve[i].size()){ mp.clear(); for(int j=2;j<=(i<<1);j++)f[j]=(f[j-1]+f[j-2])%i; for(int j=2;j<=(i<<1);j++){ if(!f[j])break; Ele temp=calc(f[j],f[j-1],i); if(mp.find(temp)==mp.end())mp[temp]=j; } for(int j=0;j<ve[i].size();j++){ Ele temp=calc(ve[i][j].a,i-ve[i][j].b,i); if(mp.find(temp)!=mp.end())ans[ve[i][j].c]=mp[temp]; } } for(int i=1;i<=n;i++)printf("%d ",ans[i]); return 0; }