P4213 【模板】杜教筛（Sum）

(color{#0066ff}{题目描述})

给定一个正整数(N(Nle2^{31}-1))

求

(egin{aligned} ans_1=sum_{i=1}^nvarphi(i) end{aligned})

(egin{aligned} ans_2=sum_{i=1}^n mu(i) end{aligned})

(color{#0066ff}{输入格式})

一共T+1行
第1行为数据组数T(T<=10)
第2~T+1行每行一个非负整数N，代表一组询问

(color{ #0066ff }{ 输出格式 })

一共T行，每行两个用空格分隔的数ans1,ans2

(color{#0066ff}{输入样例})

(color{#0066ff}{ 输出样例})

(color{#0066ff}{数据范围与提示})

(N leq 2^{31})

(color{#0066ff}{题解})

前置知识1 ：狄利克雷卷积

对于任意函数f，g，有(egin{aligned} h(i) = sum_{d|i}f(d)*g(frac{n}{d})end{aligned})

h即为f和g的卷积

常用函数

1、(i(n) = 1)

2、(id(n) = n)

3、(e(n)=left{egin{aligned}1 n = 1 \ 0 n eq 1end{aligned} ight.)

4、欧拉函数(varphi(n))

5、懵逼钨丝函数(mu(n)=left{egin{aligned}1 n = 1 \ (-1)^k n由k个不同质数相乘得到\ 0 其它情况end{aligned} ight.)

6、(sigma(n)=n的约数和)

7、(d(n)=n的约数个数)

常用卷积

1、(i*mu = e)

2、(e*a=a)

3、(mu * id= varphi)

4、(i*id=sigma)

5、(i*i=d)

6、(i*varphi=id)

杜教筛

已知(f(i))

用来求(egin{aligned}sum_{i = 1}^n f(i)end{aligned},nleq 2^{31})

定义(h(i)=(f*g)(i)=egin{aligned}sum_{d|i}f(d)*g(frac{i}{d})end{aligned})

(displaystylesum_{i=1}^nh(i))

用定义展开

(=displaystylesum_{i=1}^nsum_{d|i}g(d)fleft(frac i d ight))

d的范围也是【1.n】的，所以改成枚举d，找它的倍数，这个式子是在求和，找全了就行

(=displaystyle sum_{d=1}^ng(d)sum_{d|i}fleft(frac i d ight))

把后面变一下

(=displaystyle sum_{d=1}^ng(d)sum_{i=1}^{leftlfloorfrac n d ight floor}f( i))

然后

(=displaystyle sum_{i=1}^ng(i)Sleft(leftlfloorfrac n i ight floor ight))

所以

(displaystyle sum_{i=1}^nh(i)=sum_{i=1}^ng(i)Sleft(leftlfloorfrac n i ight floor ight))

有一个好像没用的式子

(displaystyle g(1)S(n)=sum_{i=1}^ng(i)Sleft(leftlfloorfrac n i ight floor ight)-sum_{i=2}^ng(i)Sleft(leftlfloorfrac n i ight floor ight))

上式把后面移项就成恒等式了

我们把右面第一项用刚刚的结论换走

(displaystyle g(1)S(n)=sum_{i=1}^nh(i)-sum_{i=2}^ng(i)Sleft(leftlfloorfrac n i ight floor ight))

这。。是个递归式

就没了

对于S的递归，用数列分块

一般的h和g都很好求（构造）

对于本题来说

(i*varphi=id)

所以对于(varphi)

(displaystyle S(n)=frac{n*(n+1)}{2}-sum_{i=2}^nSleft(leftlfloorfrac n i ight floor ight))

刚刚有(i*mu=e)

所以

(displaystyle S(n)=1-sum_{i=2}^nSleft(leftlfloorfrac n i ight floor ight))

没了。。。

把前(4*10^6)的东西线性筛一下

最后的复杂度(O(n^{frac{2}{3}}))~~不会证~~

#include <bits/stdc++.h>

typedef long long LL;

const int maxn = 4e6;
const int maxx = 4e6 + 10;

int in() {
	char ch; int x = 0, f = 1;
	while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
	while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return x * f;
}

bool vis[maxx];
LL phi[maxx];
int mu[maxx], pri[maxx], tot; 
std::map<int, LL> P; 
std::map<int, int> M;

void predoit() {
	phi[1] = mu[1] = 1LL;
	for(int i = 2; i <= maxn; i++) {
		if(!vis[i]) {
			pri[++tot] = i;
			phi[i] = i - 1;
			mu[i] = -1;
		}
		for(int j = 1; j <= tot && i * pri[j] <= maxn; j++) {
			vis[i * pri[j]] = true;
			if(i % pri[j] == 0) {
				phi[i * pri[j]] = phi[i] * pri[j];
				mu[i * pri[j]] = 0;
				break;
			}
			else {
				phi[i * pri[j]] = phi[i] * (pri[j] - 1);
				mu[i * pri[j]] = -mu[i];
			}
		}
	}
	for(int i = 2; i <= maxn; i++) {
		phi[i] += phi[i - 1];
		mu[i] += mu[i - 1];
	}
}

LL workphi(int now)
{
	if(now <= maxn) return phi[now];
	if(P.count(now)) return P[now];
	LL ans = now * (now + 1LL) / 2;
	for(int i = 2, lst; i <= now; i = lst + 1) {
		lst = now / (now / i);
		ans -= 1LL * (lst - i + 1LL) * workphi(now / i);
	}
	return P[now] = ans;
}

int workmu(int now)
{
	if(now <= maxn) return mu[now];
	if(M.count(now)) return M[now];
	int ans = 1;
	for(int i = 2, lst; i <= now; i = lst + 1) {
		lst = now / (now / i);
		ans -= workmu(now / i) * (lst - i + 1);
	}
	return M[now] = ans;
}

int main() {
	predoit();
	for(int T = in(); T --> 0;) {
		int n = in();
		printf("%lld %d
", workphi(n), workmu(n));
	}
	return 0;
}