LG P4213【模板】杜教筛(Sum)

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

上一篇:vue element UI按钮点击以后颜色回显


下一篇:翻转二叉树