常见算法

约 5 个字 19 行代码

gcd

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

exgcd

void exgcd(int a, int b, int* d, int* x, int* y) {
    if (!b) { *d = a; *x = 1; *y = 0; }
    else { exgcd(b, a % b, d, y, x); *y -= *x * (a / b); }
}

快速幂

int pow_mod(int a, int p, int n){
    long long res = 1;
    while (p) {
        if (p & 1) res = 1LL * res * a % n;
        a = 1LL * a * a % n;
        p >>= 1;
    }
    return (int)res;
}