线性筛

定义

线性筛用于在\(O(n)\)的时间复杂度内求出\(1\ldots n\)的积性函数值。

求解算法

经典线性筛

经典线性筛的实现见素数筛。它保证每个合数只被其最小质因子筛去一次，因此时间复杂度为 \(O(n)\)。

线性求逆元

在模质数 \(p\) 的意义下，令 \(q = \left\lfloor \frac{p}{i} \right\rfloor\)、\(r = p \bmod i\)，则 \(qi+r=p\)。两边同乘 \(i^{-1}r^{-1}\) 可得

\[ i^{-1} \equiv -q r^{-1} \equiv (p-q)r^{-1} \pmod p. \]

因此可按 \(i=2,3,\ldots,n\) 递推求出每个 \(i^{-1}\)。

线性求欧拉函数

若 \(p_j \nmid i\)，则 \(\varphi(i p_j) = \varphi(i)(p_j-1)\)；否则 \(\varphi(i p_j) = \varphi(i)p_j\)，并停止枚举后续质数。

void cal_prime_phi(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!is_composite[i]) {
            primes.push_back(i);
            phi[i] = i - 1;
        }
        for (int p : primes) {
            if (i * p > n) break;
            is_composite[i * p] = true;
            if (i % p == 0) {
                phi[i * p] = phi[i] * p;
                break;
            }
            phi[i * p] = phi[i] * (p - 1);
        }
    }
}

线性求莫比乌斯函数

对质数 \(p_j\)：若 \(p_j \mid i\)，则 \(\mu(i p_j)=0\)；否则 \(\mu(i p_j)=-\mu(i)\)。

void cal_prime_mu(int n) {
    mu[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!is_composite[i]) {
            primes.push_back(i);
            mu[i] = -1;
        }
        for (int p : primes) {
            if (i * p > n) break;
            is_composite[i * p] = true;
            if (i % p == 0) {
                mu[i * p] = 0;
                break;
            }
            mu[i * p] = -mu[i];
        }
    }
}

线性求其他积性函数

筛去 \(n\) 的同时也得到了它的最小质因子 \(p\)。结合积性函数关系 \(f(n)=f(p^k)f\left(\frac{n}{p^k}\right)\)，并记录质因子 \(p\) 的幂次 \(k\)，即可在线性筛过程中递推更多积性函数。