『算法-ACM 竞赛-数论』线性筛求积性函数的模板

ACM 常用模板合集

void sieve()
{
    tot = 1;
    memset(vis, 0, sizeof(vis));
    low[1] = 1;
    G[1] = 函数G(n) n=1时的定义
    for (int i = 2; i <= mxn; i++)
    {
        if (!vis[i])
        {
            pri[tot++] = i;
            low[i] = i;
            G[i] =  函数G(n) n=质数时的直接定义
        }

        for (int j = 1; j <= tot && pri[j] * i <= mxn; j++)
        {
            vis[i * pri[j]] = 1;
            if (i % pri[j] == 0) //不互质
            {
                low[i * pri[j]] = low[i] * pri[j];
                if (i == low[i])
                    G[i * pri[j]] = //p^K次幂，由递推求解，或者按实际意义求解
                else
                    G[i * pri[j]] = G[i / low[i]] * G[pri[j] * low[i]];
                break;
            }
            low[i * pri[j]] = pri[j];
            G[i * pri[j]] = G[i] * G[pri[j]];
        }
    }
}