【NOIP 校内模拟】k-斐波拉契（矩阵快速幂+乘法逆元）

这道题真的很好啊！刚好把这几天学的东西结合在了一起

首先我们可以发现，一个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;
}