题解 P4213 【【模板】杜教筛（Sum）】
Aleph1022
2019-10-05 18:02:57
杜教筛部分我相信大家已经讲得很清楚了。
但是——怎么这么老实啊啊啊，人家让你用杜教筛就真杜教筛啊啊啊（逃
就算不会 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$ 的前缀和即可）。
无须卡常，直接过。
代码：
```cpp
#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));
}
}
}
```