积性函数线性筛模板化写法和一些性质

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

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)$ 的。

打表程序。