P1390 公约数的和 一题双解

原文创建时间：2021-02-22 23:11:57

题目链接

P1390

题意

求
$$\displaystyle \sum_{1\leq i < j \leq n} \gcd(i,j)$$

解法一

枚举 $\gcd$，有
$$\displaystyle \sum_{d=1}^n d\sum_{j=1}^n\sum_{i=1}^{j-1}[i\perp j]$$

由定义易见，第三层枚举的和值即为 $\varphi(j)$（当 $j > 1$ 时），从而原式化为
$$\displaystyle \sum_{d=1}^n d\sum_{i=1}^n \varphi(i)$$

我们处理出 $\varphi$ 的前缀和，数论分块即可。

时间复杂度：$\mathrm{O}(n+\sqrt{n})$

注意： 这里的 $\varphi(1)$ 按原式中的意义取值 $0$。

代码

#include<bits/stdc++.h>
#define REG register

using namespace std;

namespace ACAH
{
	typedef long long ll;
	
	const int maxn = 2e6 + 7;
	
	int N;
	int pr[maxn], pc;
	bool ip[maxn];
	ll phi[maxn], ans;
	
	template<class T> inline void qread(T &x)
	{
		x = 0; REG int t = 0; REG char ch = getchar();
		while(!isdigit(ch)) t |= (ch == '-'), ch = getchar();
		while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
		x = t ? -x : x;
	}
	
	void linear_sieve()
	{
		for(REG int i = 2; i <= N; i++) {
			if(!ip[i]) pr[++pc] = i, phi[i] = i - 1;
			for(REG int j = 1; j <= pc && 1ll * i * pr[j] <= N; j++) {
				REG int cr = i * pr[j];
				ip[cr] = true;
				if(i % pr[j]) phi[cr] = phi[i] * (pr[j] - 1);
				else {phi[cr] = phi[i] * pr[j]; break;}
			}
		}
		for(REG int i = 2; i <= N; i++) phi[i] += phi[i - 1];
	}
	
	int work()
	{
		qread(N), linear_sieve();
		for(ll l = 1, r; l <= N; l = r + 1) {
			r = N / (N / l);
			ans += (l + r) * (r - l + 1) / 2 * phi[N / l];
		}
		printf("%lld", ans);
		return 0;
	}
}

int main() {return ACAH::work();}

---

解法二

这里枚举项构成斜三角。考虑将其直接扩成正方形，求解后再减掉对角线除以 $2$ 得解。

将问题枚举项扩成正方形：
$$\displaystyle \sum_{i=1}^n\sum_{j=1}^n\gcd(i,j)$$

还是先枚举 $\gcd$：
$$\displaystyle \sum_{d=1}^n d\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}[i\perp j]$$

由 $1 \ast \mu = \varepsilon$ 得
$$\displaystyle \sum_{d=1}^n d\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{k|\gcd(i,j)}\mu(k)$$

变换枚举顺序：
$$\displaystyle \sum_{d=1}^n d\sum_{k=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\mu(k)
\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}[i|k]\sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}[j|k]$$

考虑后两层枚举，其实质为 $\displaystyle \left[1,\left\lfloor\frac{n}{d}\right\rfloor\right]$ 区间中 $k$ 的因子个数。可以发现其为 $\displaystyle \left\lfloor\frac{n}{dk}\right\rfloor$，从而
$$\displaystyle \sum_{d=1}^n d\sum_{k=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\mu(k)\left(\left\lfloor\frac{n}{dk}\right\rfloor\right)^2$$

接下来，不妨设 $T = dk$：
$$\displaystyle \sum_{T=1}^n\sum_{d|T}d\mu\left(\frac{T}{d}\right)\left(\left\lfloor\frac{n}{T}\right\rfloor\right)^2$$

$$\displaystyle \sum_{T=1}^n\left(\left\lfloor\frac{n}{T}\right\rfloor\right)^2\sum_{d|T}d\mu\left(\frac{T}{d}\right)$$

考察第二层枚举，发现其为狄利克雷卷积的形式。

由 $\mu \ast id = \varphi$，原式最终化为
$$\displaystyle \sum_{T=1}^n\left(\left\lfloor\frac{n}{T}\right\rfloor\right)^2\varphi(T)$$

我们处理出 $\varphi$ 的前缀和，并作数论分块即可。

最终，减掉对角线上的值并除以 $2$，即为本题所求。显然 $\gcd(i,i) = i$，故对角线之和可以 $\mathrm{O}(1)$ 求出。

时间复杂度：$\mathrm{O}(n+\sqrt{n})$

注意： 这里的 $\varphi(1)$ 按定义意义取值 $1$。

代码

#include<bits/stdc++.h>
#define REG register

using namespace std;

namespace ACAH
{
	typedef long long ll;
	
	const int maxn = 2e6 + 7;
	
	ll N;
	int pr[maxn], pc;
	bool ip[maxn];
	ll phi[maxn], ans;
	
	template<class T> inline void qread(T &x)
	{
		x = 0; REG int t = 0; REG char ch = getchar();
		while(!isdigit(ch)) t |= (ch == '-'), ch = getchar();
		while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
		x = t ? -x : x;
	}
	
	void linear_sieve()
	{
		phi[1] = 1;
		for(REG int i = 2; i <= N; i++) {
			if(!ip[i]) pr[++pc] = i, phi[i] = i - 1;
			for(REG int j = 1; j <= pc && 1ll * i * pr[j] <= N; j++) {
				REG int cr = i * pr[j];
				ip[cr] = true;
				if(i % pr[j]) phi[cr] = phi[i] * (pr[j] - 1);
				else {phi[cr] = phi[i] * pr[j]; break;}
			}
		}
		for(REG int i = 2; i <= N; i++) phi[i] += phi[i - 1];
	}
	
	int work()
	{
		qread(N), linear_sieve();
		ans -= (1 + N) * N / 2;
		for(ll l = 1, r; l <= N; l = r + 1) {
			r = N / (N / l);
			ans += (N / l) * (N / l) * (phi[r] - phi[l - 1]);
		}
		printf("%lld", ans >> 1);
		return 0;
	}
}

int main() {return ACAH::work();}

---

可以发现，本题采用第一种方式更直观和简便。

另：也可以先 $\mathrm{O}(n)$ 线性枚举 $d$，这样做的话推导量会小一点，不过时间复杂度会变成 $\mathrm{O}(n+n\sqrt{n})$（也可以通过本题）。

---

彩蛋 / 花絮（Nothing Educational or Useful）

1. 注意第二种解法，按照我的代码 N 应开 long long，否则会炸掉第二个规模。 /kk

2. 本题只有单组数据 （太水了），结果我第一遍写时习惯性地用线性筛预处理到最大规模。结果是，机房同学写的复杂度为 $\mathrm{O}(n+n\sqrt{n})$ 的代码居然比我跑得快…… /kk/kk/kk

---

多倍经验

P1390（本题）, P1447（需推导）, SP3871, UVA11424, Project Euler 625（需杜教筛）