题解 P4213 【【模板】杜教筛（Sum）】

· · 题解

杜教筛部分我相信大家已经讲得很清楚了。
但是——怎么这么老实啊啊啊，人家让你用杜教筛就真杜教筛啊啊啊（逃
就算不会 Min25 筛洲阁筛之类的神仙筛法，也要稍微用点技巧啊啊啊！

注意到

\begin{aligned}\sum\limits_{i=1}^n\varphi(i)&=\sum\limits_{i=1}^n\sum\limits_{j=1}^i[\gcd(i,j)=1]\\&=\sum\limits_{i=1}^n\sum\limits_{j=1}^i\sum\limits_{d|\gcd(i,j)}\mu(d)\\&=\sum\limits_{d=1}^n\mu(d)\sum\limits_{i=1}^n\sum\limits_{j=1}^i[d \mathop{|} \gcd(i,j)]\\&=\sum\limits_{d=1}^n\mu(d)\sum\limits_{i=1}^{\lfloor\frac nd\rfloor} i\\&=\sum\limits_{d=1}^n\frac{\mu(d)\lfloor\frac nd\rfloor(\lfloor\frac nd\rfloor+1)}2\end{aligned}

其实就是运用了 \mu * \textbf{ID} = \varphi 的这个性质，从而简化了计算过程。
类似地，如果有 f * g = h，那么 \sum\limits_{i=1}^n h(i)=\sum\limits_{i=1}^n f(i)\sum\limits_{j=1}^{\lfloor\frac ni\rfloor} g(j)。

这样就把算 \varphi 前缀和的复杂度降到了 O(\sqrt n)（然而前提是你要算 \mu 的前缀和，于是再用杜教筛算 \mu 的前缀和即可）。
无须卡常，直接过。

代码：

#include <cstdio>
#include <cstring>
#include <bitset>
using namespace std;
const int N = 0x7fffffff;
const int MX = 5e6;
int T,n;
int vis[MX + 5],cnt,prime[MX + 5],mu[MX + 5];
long long phi[MX + 5];
int w[MX + 5];
bitset<MX + 5> v;
inline int id(int x)
{
    return n / x;
}
int smu(int n)
{
    if(n <= MX)
        return mu[n];
    if(v[id(n)])
        return w[id(n)];
    int ret = 1;
    for(register int l = 2,r;l <= n;l = r + 1)
    {
        r = n / (n / l);
        ret -= (r - l + 1) * smu(n / l);
    }
    v[id(n)] = 1;
    return w[id(n)] = ret;
}
long long ans;
int main()
{
    mu[1] = phi[1] = 1;
    for(register int i = 2;i <= MX;++i)
    {
        if(!vis[i])
            mu[prime[++cnt] = i] = -1,phi[i] = i - 1;
        for(register int j = 1;j <= cnt && i * prime[j] <= MX;++j)
        {
            vis[i * prime[j]] = 1;
            if(!(i % prime[j]))
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
            mu[i * prime[j]] = -mu[i];
        }
        mu[i] += mu[i - 1],phi[i] += phi[i - 1];
    }
    scanf("%d",&T);
    for(;T;--T)
    {
        ans = 0,v.reset(),scanf("%d",&n);
        if(n <= MX)
            printf("%lld %d\n",phi[n],mu[n]);
        else
        {
            for(register int l = 1,r;l <= n;l = r + 1)
            {
                r = n / (n / l);
                ans += (long long)(n / l) * (n / l + 1) / 2 * (smu(r) - smu(l - 1));
            }
            printf("%lld %d\n",ans,smu(n));
        }
    }
}