数论基础

质数（Prime）

只能被 1 和自身整除的大于 1 的整数。

质数判定

int is_prime(int n) {
    if (n < 2) return 0;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

埃氏筛法

int is_prime[1000001];
void sieve(int n) {
    for (int i = 2; i <= n; i++) is_prime[i] = 1;
    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = 0;
            }
        }
    }
}

最大公约数（GCD）

辗转相除法：

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

最小公倍数（LCM）

int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

快速幂

long long fast_pow(long long base, long long exp, long long mod) {
    long long result = 1;
    while (exp) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}