[WC2021] 斐波那契——数论、斐波那契数列

[WC2021] 斐波那契

题解

这里不得不向 Tiw 神下跪~
一道黑题被他讲成一道蓝题难度
根本不会做的我瞬间感觉自己降智了好多

首先发现我们要解决的是满足这个式子：
$$a{f}_{n-1}+b{f}_n=0(\mathrm{m}\mathrm{o}\mathrm{d}m)$$的最小的 $n$。

我们可以先处理一下，令 $c=\gcd (a,b,m),a^{\prime }=\frac{a}{c},b^{\prime }=\frac{b}{c},m^{\prime }=\frac{m}{c}$，然后有如下性质：
$$\begin{gathered} \gcd (\gcd (a^{\prime },m^{\prime }),\gcd (b^{\prime },m^{\prime }))=1 \\ \gcd (f_n,f_{n-1})=1 \end{gathered}$$因为取模 $m^{\prime }$ 不影响与 $m^{\prime }$ 的 $\gcd$，由 $\gcd (a^{\prime }{f}_{n-1},m^{\prime })=\gcd (b^{\prime }{f}_n,m^{\prime })$ 可得：
$$\begin{gathered} \gcd (a^{\prime },\frac{m^{\prime }}{\gcd (f_{n-1},m^{\prime })})\gcd (f_{n-1},m^{\prime })=\gcd (b^{\prime },m^{\prime })\gcd (f_n,\frac{m^{\prime }}{\gcd (b^{\prime },m^{\prime })}) \\ \Rightarrow \frac{\gcd (f_{n-1},m^{\prime })}{\gcd (f_n,\frac{m^{\prime }}{\gcd (b^{\prime },m^{\prime })})}=\frac{\gcd (b^{\prime },m^{\prime })}{\gcd (a^{\prime },\frac{m^{\prime }}{\gcd (f_{n-1},m^{\prime })})} \end{gathered}$$因为两边的分式的分子分母都互质，所以两边都是最简分式，有 $$\begin{gathered} \gcd (f_n,\frac{m^{\prime }}{\gcd (b^{\prime },m^{\prime })})=\gcd (a^{\prime },\frac{m^{\prime }}{\gcd (f_{n-1},m^{\prime })}) \\ \gcd (f_{n-1},m^{\prime })=\gcd (b^{\prime },m^{\prime }) \end{gathered}$$而我们需要的只有第二条。

令 $g=\gcd (b^{\prime },m^{\prime })$，那么有 $\frac{-a^{\prime }}{\frac{b^{\prime }}{g}}=\frac{f_n}{\frac{f_{n-1}}{g}}(\mathrm{m}\mathrm{o}\mathrm{d}\frac{m^{\prime }}{g})$，此时分母与模数互质，可以求逆元。

于是就得到一种做法：先预处理，枚举所有可能的 $m^{\prime }$（$m$ 的因子），然后枚举斐波那契数列，把相邻两项按 $g=\gcd (f_{n-1},m^{\prime })$ 分类，每一类用 map 记录到达一种 $\frac{f_n}{\frac{f_{n-1}}{g}}$ 值的最小的 $n$。由于斐波那契在模意义下循环节长度是 $O(模数)$ 的，所以预处理复杂度大概是 $m$ 的因子的和带个 $\log$，不超过 $O(m{\log }^{2}m)$。

询问直接找到对应的 $m^{\prime }$ 对应的类再在 map 里查询即可。

代码

#include<bits/stdc++.h>//JZM yyds!!
#define ll long long
#define lll __int128
#define uns unsigned
#define fi first
#define se second
#define IF (it->fi)
#define IS (it->se)
#define END putchar('\n')
#define lowbit(x) ((x)&-(x))
#define inline jzmyyds
using namespace std;
const int MAXN=114514;
const ll INF=1e18;
ll read(){
    
	ll x=0;bool f=1;char s=getchar();
	while((s<'0'||s>'9')&&s>0){
    if(s=='-')f^=1;s=getchar();}
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return f?x:-x;
}
int ptf[50],lpt;
void print(ll x,char c='\n'){
    
	if(x<0)putchar('-'),x=-x;
	ptf[lpt=1]=x%10;
	while(x>9)x/=10,ptf[++lpt]=x%10;
	while(lpt>0)putchar(ptf[lpt--]^48);
	if(c>0)putchar(c);
}
int Q,m;
unordered_map<int,unordered_map<int,int> >mp[MAXN];
ll gcd(ll a,ll b){
    return !b?a:gcd(b,a%b);}
ll exgcd(ll a,ll b,ll&x,ll&y){
    
	if(!b)return x=1,y=0,a;
	ll d=exgcd(b,a%b,y,x);
	return y-=a/b*x,d;
}
ll inv(ll a,ll p){
    
	ll x,y,d=exgcd(a,p,x,y);
	if(d!=1)return 1145141919810;
	return (x%p+p)%p;
}
int main()
{
    
	Q=read(),m=read(),mp[1][1][0]=2;
	for(int x=2;x<=m;x++)if(m%x==0){
    
		ll a=1,b=1;
		for(int i=2;;i++,swap(a,b),(b+=a)%=x){
    
			ll d=gcd(a,x),c=b*inv(a/d,x/d)%(x/d);
			if(mp[x][d].count(c))break;
			mp[x][d][c]=i;
		}
	}
	while(Q--){
    
		ll a=read(),b=read();
		if(!a){
    print(0);continue;}
		if(!b){
    print(1);continue;}
		ll d=gcd(gcd(a,b),m),k=m/d;
		a/=d,b/=d,d=gcd(b,k);
		ll c=(m-a)*inv(b/d,k/d)%(k/d);
		auto it=mp[k][d].find(c);
		if(it!=mp[k][d].end())print(IS);
		else print(-1);
	}
	return 0;
}