跳转至

1 数论

1.1 快速幂

int ksm(int x, int n = MOD - 2, int p = MOD) {
    int ans = 1;
    for (x %= p; n; n >>= 1, x = x * x % p)
        if (n & 1) ans = ans * x % p;
    return ans;
}

1.2 线性筛

预处理积性函数用，同时筛出素数。常见的有因数个数、因数和、莫比乌斯函数、欧拉函数等。

  • 若 \(p\nmid i\)，则 \(f_{p\cdot i} = f_p \cdot f_i\)。
  • 若 \(p\mid i\)，需要得到 \(f_{p^k i} \rightarrow f_{p^{k+1}i}\) 的递推关系。

以下是求解因数个数以及因数和的模板。

vector<int> primes, minp;
vector<int> cnt;           // cnt[i] = 指数 e（i 中最小质因子的幂）
vector<long long> pw;      // pw[i] = p^e（对应最小质因子部分）
vector<long long> dcnt;    // 约数个数 d(n)
vector<long long> dsum;    // 约数和 sigma(n)

void sieve(int n) {
    primes.reserve(2 * n / __lg(n));
    minp.assign(n + 1, 0);
    cnt.assign(n + 1, 0);
    pw.assign(n + 1, 0);
    dcnt.assign(n + 1, 0);
    dsum.assign(n + 1, 0);

    minp[1] = 1;
    cnt[1] = 0;
    pw[1] = 1;
    dcnt[1] = 1;   // d(1) = 1
    dsum[1] = 1;   // sigma(1) = 1

    for (int i = 2; i <= n; ++i) {
        if (!minp[i]) {
            primes.emplace_back(i);
            minp[i] = i;
            cnt[i] = 1;      
            pw[i] = i;       
            dcnt[i] = 2;      
            dsum[i] = 1 + (long long)i; 
        }
        for (int p : primes) {
            long long ip = 1LL * i * p;
            if (p > minp[i] || ip > n) break;
            minp[ip] = p;
            if (i % p == 0) {
                cnt[ip] = cnt[i] + 1;
                pw[ip]  = pw[i] * p;
                dcnt[ip] = dcnt[i] / (cnt[i] + 1) * (cnt[i] + 2);
                dsum[ip] = dsum[i] / (1 + pw[i]) * (1 + pw[ip]);
            } else {
                cnt[ip] = 1;
                pw[ip]  = p;
                dcnt[ip] = dcnt[i] * 2;  
                dsum[ip] = dsum[i] * (1 + (long long)p);
            }
        }
    }
}

1.3 欧拉函数

1到n中与n互素的整数个数，是积性函数。

1.3.1 单点查

用到公式 \(\varphi(n)=n\prod_{i=1}^{m}(1-\frac{1}{p_i})\)。m为质因数的个数。复杂度 \(O(\sqrt{n})\)。

long long phi(long long n) {
    long long res = n;
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0) n /= i;
            res = res / i * (i - 1);
        }
    }
    if (n > 1) res = res / n * (n - 1);
    return res;
}

1.3.2 线性筛

用到性质 \(\varphi(p^k) = p^k - p^{k-1}\)。复杂度\(O(n)\)。

vector<int> primes, minp, phi;
void sieve(int n) {
    primes.reserve(2 * n / __lg(n));
    minp.assign(n + 1, 0);
    phi.assign(n + 1, 0);
    minp[1] = phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!minp[i]) {
            primes.emplace_back(i);
            minp[i] = i;
            phi[i] = i - 1;
        }
        for (int p : primes) {
            if (p > minp[i] or i * p > n) break;
            minp[i * p] = p;
            if (i % p == 0) {
                phi[i * p] = phi[i] * p;
            } else {
                phi[i * p] = phi[i] * phi[p];
            }
        }
    }
}

1.3.3 欧拉反演

\[ n = \sum_{d\mid n} \varphi(d) \]
\[ \gcd(a, b) = \sum_{d}[d\mid a][d\mid b]\varphi(d) \]

1.4 莫比乌斯函数

\[ \mu(n) = \begin{cases} 1 & \text{如果 } n = 1, \\ 0 & \text{如果 } n \text{ 有一个平方的质因子}, \\ (-1)^k & \text{如果 } n \text{ 是 } k \text{ 个不同质数的乘积}. \end{cases} \]

1.4.1 线性筛

void sieve(int n) {
    minp.assign(n + 1, 0);
    miu.assign(n + 1, 0);
    miu[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!minp[i]) {
            primes.emplace_back(minp[i] = i);
            miu[i] = -1;
        }
        for (int p : primes) {
            if (p * i > n or p > minp[i]) break;
            minp[i*p] = p;
            miu[i*p] = i % p ? -miu[i] : 0;
        }
    }
}

1.4.2 莫比乌斯反演

\[ \sum_{d|n} \mu(d) = [n = 1] \]
\[ [\gcd(i, j) = 1] = \sum_{d|\gcd(i, j)} \mu(d) \]

1.5 和式变换技巧

  1. 替换条件式 $$ \sum_{i=1}^{n} \sum_{j=1}^{m} \sum_{d|\gcd(i,j)} d = \sum_{i=1}^{n} \sum_{j=1}^{m} \sum_{d=1}^{n} [d | i][d | j]d $$

  2. 替换指标变量 $$ \sum_{i=1}^{n} \sum_{j=1}^{m} [\gcd(i,j) = k] = \sum_{ik=1}^{n} \sum_{jk=1}^{m} [\gcd(ik,jk) = k] $$

  3. 交换求和次序 $$ \sum_{i=1}^{n} \sum_{j=1}^{m} A(i)B(j) = \sum_{j=1}^{m} \sum_{i=1}^{n} A(i)B(j) $$

  4. 分离变量 $$ \sum_{i=1}^{n} \sum_{j=1}^{m} A(i)B(j) = \sum_{i=1}^{n} A(i) \sum_{j=1}^{m} B(j) $$

1.6 扩展欧几里得算法 （exgcd）

// gcd(x, y) = a * x + b * y, return gcd(x, y)
int exgcd(int x, int y, int &a, int &b) {
    if (!y) {
        a = 1, b = 0;
        return x;
    }
    int d = exgcd(y, x % y, b, a);
    b -= a * (x / y);
    return d;
}