Loading... ## 素数 <!--more--> miller_rabm素数测试 ## gcd(a,b) ```cpp 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$ ```cpp 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 14, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏