Codeforces 919E Congruence Equation

题目链接http://codeforces.com/contest/919/problem/E

题意:略。

思路:首先我们用欧拉公式降幂得到na^n\equiv n*a^{n\bmod (p-1)}(\bmod p),那么我们可以很清楚地知道na^n在模p意义下的周期就是p\times (p-1),因为n的周期是p,而a^n的周期由降幂公式可以知道是p-1,然后我们令n=i\times (p-1)+j,那么上述同余方程就可以转化为na^j\equiv b(\bmod p),我们预处理出a^j的逆元a^{-j},上述同余方程转化为n\equiv a^{-j}b(\bmod p),同时还有一条显然的限制方程n\equiv j(\bmod (p-1)),由中国剩余定理我们可以知道n为模p\times (p-1)的意义下有一个唯一解,然后我们枚举j就可以知道一个周期内有多少满足条件的解,用n+p\times (p-1)\times t\leq x这个不等式就可以求出我们的答案了,时间复杂度根据你求逆元的时间复杂度而定。

时间复杂度:O(p*log^2 p)

ll a,b,p,x;
ll ksm(ll a,ll n){
    ll res=1;
    while (n){
        if (n&1) res=(res*a)%p;
        a=(a*a)%p;
        n>>=1;
    }
    return res;
}
int main(){
    read(a),read(b),read(p),read(x);
    ll ans=0;
    ll inv=ksm(p-1,p-2);
    //DBN1(inv);
    for (int i=1;i<=p-1;i++){
        ll tmp=ksm(ksm(a,i),p-2)*b%p;
        ll n=(i*p+tmp*(p-1)*inv)%(p*(p-1));
        ans+=(x-n+p*(p-1))/(p*(p-1));
    }
    printf("%lld\n",ans);
    return 0;
}

时间复杂度:O(p)

int i;
ll a,b,p,x,ans,A[maxn];
int main(){
    read(a),read(b),read(p),read(x);
    for (A[0]=i=1;i<p;i++) A[i]=A[i-1]*a%p;
    for (i=1;i<p;i++){
        ll tmp=b*A[p-1-i]%p;//根据费马小定理推推就推出来了
        ll n=(i*p+tmp*(p-1)*(p-1))%(p*(p-1));
        ans+=(x-n+p*(p-1))/(p*(p-1));
    }
    printf("%lld\n",ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注