#C231109B. k-斐波那契

标签（Label）

数学
exgcd

网址（Website）

题目详情 - k-斐波那契 - Super

题解 - k-斐波那契 - Super

题目（Problem）

$f(x)$ 斐波拉契数列定义如下：
$$
f(n)=\begin{cases}
K, & \text{(n=0)} \\
K, & \text{(n=1)} \\
((f(n-1)+f(n-2))\mod P & (n > 1)
\end{cases}
$$
已知$f(n)=1$，求$[0,P)$内所有可能的$K$。

范围：$n, P ≤ 10^9$。

题解（Solution）

$\qquad$除去 $k$ 对函数 $f(n)$ 带来的影响，该函数就是标准的斐波那契数列，考虑到 $n$ 的范围，用矩阵就可以做出来，设斐波那契数列函数为 $g(n)$ 则有：$f(n)=K\times g(n)$ 。

$\qquad$该题转化为：求得一个正整数 $K\in[1,p]$ ，满足：$K\times g(n)\equiv 1(mod\ p)$ ，则可以得出：

$\qquad\qquad K\times g(n)-1\equiv0 (mod\ p)\Rightarrow K\times g(n)-1=s\times p\Rightarrow K\times g(n)-s\times p=1$

$\qquad$ 扩欧计算即可，因为右边 $=1$，所以 $mod\ p$下只有一组。

$\qquad$注意：其实可以直接从 $K\times g(n)\equiv1(mod\ p)$ 推出 $K\times g(n)+s\times p=1$ ，符号并不影响最终的答案，因为我们最后要求的是 $K$ 的正整数解，在 $(K mod\ p+p)\ mod\ p$ 后，答案是等价的。

代码（Code）

$\qquad$对于解线性同余方程，对于 $K\times g(n)+s\times p=1$ ，直接用函数 $exgcd(\ g(n)\ ,p\ ,K\ ,s\ )$ 可以直接求出答案 $K$ ，之后再取模即可。

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define int long long
inline int input(){int x;return cin>>x,x;}

int n,p;

struct Jz{
	int a[4][4],n=2,m=2;
	Jz(){memset(a,0,sizeof(a));}
	Jz operator*(Jz y){
		Jz res;For(k,1,2) For(i,1,2) For(j,1,2){
			res.a[i][k]=(res.a[i][k]+a[i][j]*y.a[j][k]%p)%p;
		}return res;
	}
};

inline Jz ksm(int k){
	Jz res;res.a[1][1]=res.a[2][2]=1;
	Jz x;x.a[1][1]=x.a[1][2]=x.a[2][1]=1;
	while(k){
		if(k&1) res=res*x;
		x=x*x,k>>=1;
	}return res;
}

inline int g(int a,int b,int &x,int &y){
	if(!b) return x=1,y=0,a;
	int d=g(b,a%b,y,x);
	y-=a/b*x;return d;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	string str("kfib");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
	cin>>n>>p;
	Jz ans=ksm(n);
	
	int a=ans.a[1][1],k,b;
	g(a,p,k,b);
	cout<<(k%p+p)%p<<'\n';
	
    //这是另一种（标准的）方法
//	int a=1,b=ans.a[1][1],c=p,X,Y;
//	int d=g(b,c,X,Y),r=c/d;
//	if(a%d) cout<<"None\n";
//	else cout<<(a/d*X%r+r)%r<<'\n';
	return 0;
}