线性筛和积性函数

用于线性预处理积性函数的值。

引入一个概念 low 表示一个数的最小质因子的幂。因为一个数只会被它的最小质因子筛出，所以 primes[j] * i 的最小质因子为 primes[j] ，当 i % primes[j] == 0 时，说明 i 也有因子 primes[j]，而 i 是primes[j] * i 的因数，所以 i 的最小质因子也为 prmies[j]，积性函数中计算 f(a * b) = f(a) * f(b) 的条件是 a 与 b 互质，所以将 low[i] 从 a 中分给 b ，两者积不变，保证答案一样，而 a / low[i] 中不含有质因子 primes[j] ，而 b * low[i] 只含有质因子 primes[j] ，从而保证它们互质。

未筛过的数一定没有 low ，从而代替 vis 数组。

Take phi as an example.

查看代码

void init()
{
    f[1] = 1; // define f[1]
    low[1] = 1;
    for (int i = 2; i < N; i++)
    {
        if (!low[i])
        {
            primes[++cnt] = i;
            f[i] = i - 1; // define f[prime]
            low[i] = i;
        }
        for (int j = 1; j <= cnt && i * primes[j] < N; j++)
        {
            if (i % primes[j] == 0)
            {
                if (low[i] == i)
                    f[i * primes[j]] = f[i] * primes[j]; // define f[prime ^ k]
                else
                    f[i * primes[j]] = f[i / low[i]] * f[primes[j] * low[i]];
                low[i * primes[j]] = low[i] * primes[j];
                break;
            }
            f[i * primes[j]] = f[i] * f[primes[j]];
            low[i * primes[j]] = primes[j];
        }
    }
}