积性函数线性筛

robinyqc · 2024-11-25 17:15:03 · 算法·理论

我忽然想起来可以写一个积性函数线性筛。所以我写了一个。

template<typename T, typename F>
vec<T> multiplicative_function_table(u32 n, F &&g)
{
    vec<u32> prime;
    vec<bool> vis(n + 1);
    prime.reserve(n / 15);
    vec<T> res(n + 1);
    res[1] = T(1);
    for (u32 i = 2, t, k, ni; i <= n; i++) {
        if (!vis[i]) {
            prime.emplace_back(i);
            res[i] = g(i, 1);
        }
        for (u32 j: prime) {
            if (i * j > n) break;
            vis[i * j] = true;
            t = i / j;
            if (i == t * j) {
                k = 1;
                do ni = t, t /= j, k++;
                while (ni == t * j);
                res[i * j] = res[ni] * g(j, k);
                break;
            }
            res[i * j] = res[i] * g(j, 1);
        }
    }
    return res;
}

传入一个函数（或者仿函数） g，g(x, y) 返回 f(x^y) 即可（保证 x 是质数）。

这段代码有个比较直觉的地方是，当 i % j == 0 （也就是 i == t * j）的时候，我直接暴力将 i 分解为了 j^k \times x。感觉这个复杂度就很对，总复杂度是线性的。

经过打表，我认为这玩意就是对的。我打出的表显示，1 到 n 的 k 之和（也就是，每个数的最小质因子个数之和）约等于 1.612n。n 从 10 开始一直到 10^8，比值都保持在 1.612。

这个性质的意义是，线性筛积性函数的限制更松了：若求 f(p^k) 的复杂度是 O(k)，那么筛出 [1, n] 的 f 值也是 O(n) 的。

打表程序。