#P10252. k-斐波那契

前言（Front talk)

数学一定要好好学，虽然学的时候比较难懂，但是想出来方法就会非常简单

网址（Website）

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

题解 - k-斐波那契 - Super

题目（Problem）

斐波拉契数列定义如下：

已知，求内所有可能的。

范围：。

题解（Solution）

除去对函数带来的影响，该函数就是标准的斐波那契数列，考虑到的范围，用矩阵就可以做出来，设斐波那契数列函数为则有：。

该题转化为：求得一个正整数，满足：，则可以得出：

扩欧计算即可，因为右边，所以下只有一组。

注意：其实可以直接从推出，符号并不影响最终的答案，因为我们最后要求的是的正整数解，在后，答案是等价的。

代码（Code）

对于解线性同余方程，对于，直接用函数可以直接求出答案，之后再取模即可。

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