「CF919E」Congruence Equation

Source

CF919E

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)$

1
2
3
4
5
6
7
8
9
10
11
12
13
void main()
{
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);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/16c0.html
转载请注明出处,谢谢!