自动搬运

查看原文

来自洛谷，原作者为

	Great_Influence **

搬运于2025-08-24 21:55:45，当前版本为作者最后更新于2018-01-03 21:37:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

参加div1后唯一A的题目。。。。。。

设$a_2=x$。先推式子，暴力算出前几项，发现

$a_z=iFi[z-3]+Fi[z-2]x$

(Fi为斐波那契数列，且Fi[0]=1)

所以

$a_k=iFi[k-3]+Fi[k-2]x\equiv m\pmod p$

即

$Fi[k-2]x\equiv m-iFi[k-3]\pmod p$

设$Q=m-iFi[k-3]$，则

$Fi[k-2]x\equiv Q\pmod p$

$Fi[k-2]x=Q+py$

$Fi[k-2]x-py=Q$

同余方程，用扩展欧几里得求解得出x的通解公式，在利用通解公式来计算x在[l,r]内解个数。时间复杂度，$O(log_2k)$。

代码：

    #include<bits/stdc++.h>
    #include<cctype>
    #define For(i,a,b) for(i=(a),i##end=(b);i<=i##end;++i)
    #define Forward(i,a,b) for(i=(a),i##end=(b);i>=i##end;--i)
    #define Rep(i,a,b) for(register int i=(a),i##end=(b);i<=i##end;++i)
    #define Repe(i,a,b) for(register int i=(a),i##end=(b);i>=i##end;--i)
    #define Chkmax(a,b) a=a>(b)?a:(b)
    using namespace std;
    template<typename T>inline void read(T &x){
        T s=0,f=1;char k=getchar();
        while(!isdigit(k)&&k^'-')k=getchar();
        if(!isdigit(k)){f=-1;k=getchar();}
        while(isdigit(k)){s=s*10+(k^48);k=getchar();}
        x=s*f;
    }
    void file(void){
    #ifndef ONLINE_JUDGE
        freopen("water.in","r",stdin);
        freopen("water.out","w",stdout);
    #endif
    }
    long long g,l,r,k,mod,m;
    void init()
    {
        read(g);read(l);read(r);read(k);read(mod);read(m);
    }
    long long a[2][2]={0ll,1ll,1ll,1ll},s[2][2],base[2][2];
    inline void tim(long long a[][2],long long b[][2])
    {
        long long c[2][2]={0ll};
        Rep(i,0,1)Rep(j,0,1)Rep(k,0,1)(c[i][j]+=a[i][k]*b[k][j])%=mod;
        Rep(i,0,1)Rep(j,0,1)a[i][j]=c[i][j];
    }
    long long ext_gcd(long long a,long long b,long long &x,long long &y)
    {
        if(!b){x=1ll;y=0ll;return a;}
        long long ans=ext_gcd(b,a%b,x,y);
        swap(x,y);
        y=y-a/b*x;
        return ans;
    }
    void solve()
    {
        --k;
        memcpy(base,a,sizeof a);
        s[0][0]=s[1][1]=1;s[0][1]=s[1][0]=0;
        for(;k;k>>=1,tim(base,base))if(k&1)tim(s,base);
        g%=mod;
        m-=s[0][0]%mod*g%mod;m%=mod;m+=mod;m%=mod;
        long long y,z;
        long long gcd=ext_gcd(s[1][0],mod,y,z);
        if(m%gcd!=0)
        {
            printf("0\n");
            return;
        }
        y*=m/gcd;
        if(y>=0)(y%=(mod/gcd))-=mod/gcd;
        printf("%lld\n",(r-y)/(mod/gcd)-(l-1-y)/(mod/gcd));
    }
    int main(void){
        file();
        int _;
        read(_);
        while(_--)
        init(),
        solve();
        return 0;
}