数论基础：质数、约数、欧几里得算法，信奥必备的数学知识

质数判断

// 判断单个质数 O(√n)
bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

// 筛法求1..n的所有质数 O(n log log n)
const int N = 1000000;
bool isPrime[N+1];
vector<int> primes;

void sieve() {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= N; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
            for (int j = i * 2; j <= N; j += i)
                isPrime[j] = false;
        }
    }
}

最大公约数（GCD）

// 欧几里得算法 O(log n)
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;  // 先除后乘，防止溢出
}

扩展欧几里得算法

// 求解 ax + by = gcd(a,b) 的一组解
int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

应用：求解同余方程、模逆元。

约数相关

// 求所有约数 O(√n)
vector<int> getDivisors(int n) {
    vector<int> res;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            res.push_back(i);
            if (i != n / i) res.push_back(n / i);
        }
    }
    return res;
}

// 约数个数定理
int countDivisors(int n) {
    int cnt = 1;
    for (int p : primes) {
        if (p * p > n) break;
        int power = 0;
        while (n % p == 0) {
            n /= p;
            power++;
        }
        cnt *= (power + 1);
    }
    if (n > 1) cnt *= 2;
    return cnt;
}

快速幂

// 计算 a^b % mod  O(log b)
long long qpow(long long a, long long b, long long mod) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

应用：大数幂运算、模逆元计算。