素数

miller_rabm素数测试

gcd(a,b)

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$

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互质的才有逆元。


中国剩余定理

Last modification:March 14th, 2020 at 09:10 pm