bzoj5131: [CodePlus2017年12月]可做题2

画一下柿子就可以变成这样：fib[k-1]*x=m-fib[k-2]*a1(mod p) 求l<=x<=r满足柿子的方案数

然后就exgcd求一下

(我真是二的一批学了个斐波那契的通项公式取模不了炸long double了一脸懵就是没想矩阵乘法)

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;

LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(a==0)
    {
        x=0,y=1;
        return b;
    }
    else
    {
        LL tx,ty;
        LL d=exgcd(b%a,a,tx,ty);
        x=ty-b/a*tx;
        y=tx;
        return d;
    }
}

LL p;
struct Matrix
{
    LL mp[3][3];
    friend Matrix operator *(Matrix a,Matrix b)
    {
        Matrix c;
        memset(c.mp,0,sizeof(c.mp));
        for(int i=1;i<=2;i++)
            for(int j=1;j<=2;j++)
                for(int k=1;k<=2;k++)
                    c.mp[i][j]=(c.mp[i][j]+a.mp[i][k]*b.mp[k][j])%p;
        return c;
    }
}ret,A;
LL getfib(LL k)
{
    ret.mp[1][1]=1,ret.mp[1][2]=1;
    ret.mp[2][1]=0,ret.mp[2][2]=0;
    A.mp[1][1]=0,A.mp[1][2]=1;
    A.mp[2][1]=1,A.mp[2][2]=1;
    
    k=k-2;
    while(k!=0)
    {
        if(k%2==1)ret=ret*A;
        A=A*A;k/=2;
    }
    return ret.mp[1][2];
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        LL a1,l,r,k,m;
        scanf("%lld%lld%lld%lld%lld%lld",&a1,&l,&r,&k,&p,&m);
        LL G=((m-(getfib(k-2)%p)*(a1%p)%p)%p+p)%p;
        
        LL A=getfib(k-1)%p,B=p,K=G,x,y;
        LL d=exgcd(A,B,x,y);
        if(K%d!=0)printf("0
");
        else
        {
            x=(x*(K/d)%(B/d)+(B/d))%(B/d);
            if(x<=r)
            {
                if(l-1<x)printf("%lld
",(r-x)/(B/d)+1);
                else printf("%lld
", ((r-x)/(B/d)+1) - ((l-1-x)/(B/d)+1) );
            }
            else printf("0
");
        }
    }
    return 0;
}