\(\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));

	}

}

巴特西

LG P4213【模板】杜教筛（Sum）

\(\text{Problem}\)

\(Solution\)

\(\text{Code}\)

最新文章

热门文章