\(\text{Problem}\)
求
\[\sum_{i=1}^n \varphi(i)
\]
和
\[\sum_{i=1}^n \mu(i)
\]
\(1 \le n < 2^{31}\)
\(Solution\)
终于开始学杜教筛了！！！
求积性函数 \(f\) 的前缀和，杜教筛可以低于线性
考虑卷积，构造积性函数 \(h = f * g\)
然后套路地推出一个重要的结论
\[g(1)S(n)=\sum_{i=1}^n(f*g)(i)-\sum_{i=2}^n S(\lfloor \frac n i \rfloor)
\]
这是一个递归式，快速计算这个式子
要能快速 \(h\) 的前缀和，最后的式子整出分块
提前筛出 \(n^{\frac 2 3}\) 以内 \(f\) 的前缀和，算到直接使用
用 \(\text{unordered_map}\) 存下已经计算过的 \(f\) 的前缀和，进行记忆化
然后对于本题就是利用
\[\varphi * I = ID
\]
\[\mu * I = \epsilon
\]
\(\text{Code}\)
#include<cstdio>
#include<tr1/unordered_map>
#define LL long long
using namespace std;
tr1::unordered_map<int, LL> S_phi;
tr1::unordered_map<int, int> S_mu;
const int MAXN = 3e6;
int vis[MAXN + 5], mu[MAXN + 5], prime[MAXN], totp;
LL phi[MAXN + 5];
inline void sieve()
{
vis[1] = mu[1] = phi[1] = 1;
for(register int i = 2; i <= MAXN; i++)
{
if (!vis[i]) prime[++totp] = i, mu[i] = -1, phi[i] = i - 1;
for(register int j = 1; j <= totp && prime[j] * i <= MAXN; j++)
{
vis[i * prime[j]] = 1;
if (i % prime[j]) phi[i * prime[j]] = phi[i] * phi[prime[j]], mu[i * prime[j]] = -mu[i];
else{phi[i * prime[j]] = phi[i] * prime[j]; break;}
}
}
for(register int i = 1; i <= MAXN; i++) mu[i] += mu[i - 1], phi[i] += phi[i - 1];
}
LL Sum_phi(LL n)
{
if (n <= MAXN) return phi[n];
if (S_phi[n]) return S_phi[n];
LL res = n * (n + 1) / 2, j;
for(register LL i = 2; i <= n; i = j + 1)
{
j = n / (n / i);
res -= (j - i + 1) * Sum_phi(n / i);
}
return S_phi[n] = res;
}
int Sum_mu(LL n)
{
if (n <= MAXN) return mu[n];
if (S_mu[n]) return S_mu[n];
LL res = 1, j;
for(register LL i = 2; i <= n; i = j + 1)
{
j = n / (n / i);
res -= (j - i + 1) * Sum_mu(n / i);
}
return S_mu[n] = res;
}
int main()
{
sieve();
int T; scanf("%d", &T);
for(; T; --T)
{
LL n; scanf("%lld", &n);
printf("%lld %d\n", Sum_phi(n), Sum_mu(n));
}
}