P4031 [Code+#2] 可做题2

· · 题解

可做题。

注意到 \forall k\in \mathbb{N^*} ，有 a_k=\alpha(k)a_1+\beta(k)a_2.

尝试把系数关于 k 的表达式求出来。

赋值法，简单令 a_1=1,a_2=0 可推得 \alpha(x)=a_x=\text{Fib}(x-2)，同理推得 \beta(x)=a_x=\text{Fib}(x-1)。^\dagger

于是就有：

\alpha(k)a_1+\beta(k)a_2 &\equiv a_k &\pmod p\\ \text{Fib}(k-2)a_1+\text{Fib}(k-1)a_2&\equiv a_k &\pmod p \\ \text{Fib}(k-1)a_2&\equiv a_k -\text{Fib}(k-2)a_1 &\pmod p\\ \text{Fib}(k-1)a_2+yp&= a_k -\text{Fib}(k-2)a_1 \end{aligned}

令等号右边为 A, 将 a_2,y 看做未知数，利用扩展欧几里得可求解 a_2 的 1 个特解 a_2'，全体解有形式 a_2=a_2'+\dfrac{A}{\gcd(\text{Fib}(k-1),p)}n,\ (n\in\mathbb{Z})。

题目要求求解满足 a_2\in[l,r] 的解的个数，于是我们利用整点个数公式得到答案.

值得注意的是，此处 k 值较大，需要用矩阵加速递推。

code:

#include<bits/stdc++.h>
using namespace std;

#define int long long

int p;

struct Mat {
    int a[2][2];
    Mat(){memset(a,0,sizeof a);}
    Mat operator*(const Mat& b) const {
        Mat ret;
        for(int i=0;i<=1;i++) {
            for(int j=0;j<=1;j++) {
                for(int k=0;k<=1;k++) {
                    ret.a[i][j]+=a[i][k]*b.a[k][j];
                    ret.a[i][j]%=p;
                }
            }
        }
        return ret;
    }

    Mat qpow(int p) {
        Mat ret,tmp=*this;
        ret.a[1][1]=1;
        ret.a[0][0]=1;
        while(p>0) {
            if(p&1) ret=ret*tmp;
            p>>=1;
            tmp=tmp*tmp;
        }
        return ret;
    }
};

void exgcd(int a,int b,int &g,int &x,int &y) {
    if(b==0) {
        g=a,x=1,y=0;
        return;
    }
    exgcd(b,a%b,g,y,x);
    y-=a/b*x;
}

main() {
    Mat base,trans;
    base.a[0][1]=1;
    trans.a[0][0]=0;
    trans.a[0][1]=trans.a[1][0]=trans.a[1][1]=1;
    int T;
    cin>>T;
    while(T--) {
        int f,l,r,k,m;
        cin>>f>>l>>r>>k>>p>>m;
        Mat res=trans.qpow(k-1);
        f%=p;
        //?*ra[1]-_p==A
        int x=0,_=0,g,A=(m-(res.a[0][0]*f%p)+p)%p;
        exgcd(res.a[0][1],p,g,x,_);
        if(A%g) {
            cout<<"0\n";
            continue;
        }
        x *= (A / g), p /= g;
        if(x >= 0) x = (x % p - p);
        cout<<(r - x) / p - (l - 1 - x) / p<<'\n';
    }
}

\dagger Hint: | x | \cdots | -1 | 0 | 1 | 2 | 3 |\cdots| | :-: | :-:|:-:|:-:|:-:|:-:|:-:|:-:| | \text{Fib}(x) | \cdots | 1| 0|1|1|2|\cdots|

update 2024/08/16: fixed code.