首页 > itarticle > 「cf919e」congruence equation

「cf919e」congruence equation

admin 11月 13, 2020 0

Source

Hint

请先思考后再展开

$(n%p)a^{n%(p-1)}=b$
考虑枚举指数求系数，然后判断n的合法性

Solution

请先思考后再展开

$n=A(p-1)+i=Bp+j$
exgcd解 $A(p-1)-Bp=j-i$
并不需要真的exgcd
时间复杂度 $O(nlogn)$

void ()
{
    ll a=qread(),b=qread();MOD=qread();ll mx=qread();
    ll cnt=0;
    for(ll i=0,now=1;i<MOD-1;i++,now=now*a%MOD)
    {
        ll j=b*invm(now)%MOD;
        ll B=-(j-i),n=B*MOD+j,t=MOD-1,gg=MOD*t;n=(n%gg+gg)%gg;
        if(n==0) n=gg;
        if(n>=1 and n<=mx) cnt+=1+(mx-n)/gg;
    }
    write(cnt);
}