题解 P4031 【「CodePlus 2017 12 月赛」可做题2】

Great_Influence · 2018-01-03 21:37:37 · 题解

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

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

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

所以

即

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

同余方程，用扩展欧几里得求解得出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;
}