这道题真的很好啊！刚好把这几天学的东西结合在了一起
首先我们可以发现，一个k-斐波拉契数列的每一项就是普通的斐波拉契数列的倍数
因此问题转变成了k * f[n] =1 (mod p) 求k
卧槽？这不就是求f[n]在mod p意义下的乘法逆元吗？？
卧槽？f[n]可以用矩阵快速幂跑出？？右转洛谷P1962
卧槽？？变一下形 kf[n]+yp=1 不就是一个扩欧吗？？？
卧槽？？？根据定理当gcd(f[n],p)=1的时候原方程才有解，也就是说如果不等于1的话就输出“None”
卧槽？？？？？？？由于f[n]在mod p意义下 在[0,p)内的乘法逆元只有一个 那所以只有一个解？？？？？？？
多提一句 拓展欧几里得算法计算逆元 常常会搞出负数 但是由于逆元之间的间距刚好就是模数p 所以只需要在最后一句话添上(x%p+p)%p即可（因为c++负数取模与数学规定不一样） 代码仅供参考 不保证能否AC（我tm没地方交啊啊啊啊啊啊）
#include<iostream> #define ll long long using namespace std; struct matrix { ll m[105][105]; }; ll n=2,p,k; matrix base; matrix mul(matrix A,matrix B) { matrix C; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { C.m[i][j]=0; } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { for(int k=1;k<=n;k++) { C.m[i][j]=(C.m[i][j]+A.m[i][k]*B.m[k][j])%p; } } } return C; } matrix quickpow(matrix A,ll y) { matrix ans; //构造单位矩阵 for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i==j) ans.m[i][j]=1; else ans.m[i][j]=0; } } while(y) { if(y&1) ans=mul(ans,A); A=mul(A,A); y>>=1; } return ans; } inline int exgcd(int a,int b,int &x,int &y) { if(b==0) { x=1; y=0; return a; } int r=exgcd(b,a%b,x,y); int temp=x; x=y; y=temp-a/b*y; return r; } int main() { cin>>k>>p; base.m[1][1]=1,base.m[1][2]=1,base.m[2][1]=1,base.m[2][2]=0; base=quickpow(base,k+1); int fibn=base.m[2][1]; int x,y; if(exgcd(fibn,p,x,y)!=1) cout<<"None"; else cout<<(x%p+p)%p; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9697214.html
