zkw一课——数论

素数

miller_rabm素数测试

gcd(a,b)

1
2
3
4
int gcd(int a, int b){
if(b == 0) return a;
return gcd(b, a % b);
}

Exgcd

$ax+by=(a,b)$

想让$4x+7y=1$
$4(x+y)+3y=1$
$(x+y)+3(2x+y)=1$

1
2
3
4
5
6
int64 exgcd(int64 a, int64 b, int64 *x, int64 *y){
if(b == 0) {*x = 1; *bx = 0; return a}
int ans = exgcd(b, a % b, y, x);
*y -= a / b * *x;
return ans;
}

$ax+by=(a,b)$
解出$x_0,y_0$
通解:
$x=x_0-bt$
$y=y_0+at$

乘法逆元

$a^{-1} a \equiv 1(\mod n)$
例如$3 \times 7\equiv 1(\mod 20)$

$ab\equiv 1 (\mod n)$
$n|ab-1$
$nk=ab-1$
$ab-nk=1$
exgcd


模p时,$1 到 p$都有逆元。
模n时,与n互质的才有逆元。


中国剩余定理

# 数论

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×