「SOL」旧试题 (LOJ/SDOI)

数论+图论，妙不可言

---

# 题面

给定 $A,B,C$，求：

$$\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C\sigma_0(ijk)$$

数据规模：$A,B,C\le 2\times10^5$。

---

# 解析

显然 $A,B,C$ 三者等价，不妨设 $A$ 是最大的

关于 $\sigma_0$，有一个众所周知（比如我就不知道） 的结论：

$$\sigma_0(ab)=\sum_{i\mid a}\sum_{j\mid b}[i\bot j]$$

三个数也是一样的，

$$\sigma_0(abc)=\sum_{i\mid a}\sum_{j\mid b}\sum_{k\mid c}[i\bot j][j\bot k][k\bot i]$$

于是直接代回我们要求的式子：

$$\begin{aligned} &\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C\sum_{u\mid i}\sum_{v\mid j}\sum_{w\mid k}[u\bot v][v\bot w][w\bot u]\\ =&\sum_{u=1}^A\sum_{v=1}^B\sum_{w=1}^C[u\bot v][v\bot w][w\bot u]\left\lfloor\frac{A}{u}\right\rfloor\left\lfloor\frac{B}{v}\right\rfloor\left\lfloor\frac{C}{w}\right\rfloor \end{aligned}$$

记 $[a,b]$ 为 $a, b$ 的最小公倍数。两数互质的条件可以进行反演：

$$\begin{aligned} \sum_{a}\sum_{b}\sum_{c}\mu(a)\mu(b)\mu(c)\sum_{[a,b]\mid u}\left\lfloor\frac{A}{u}\right\rfloor\sum_{[b,c]\mid v}\left\lfloor\frac{B}{v}\right\rfloor\sum_{[c,a]\mid w}\left\lfloor\frac{C}{w}\right\rfloor \end{aligned}$$

定义 $f_b(a)$ 如下：

$$f_b(a)=\sum_{a\mid i}\left\lfloor\frac{b}{i}\right\rfloor$$

可以 $O(A\ln A)$ 预处理出 $f_A(x), f_B(x), f_C(x)$，于是要求的答案就是

$$\sum_{a}\sum_{b}\sum_{c}\mu(a)\mu(b)\mu(c)f_A([a,b])f_B([b,c])f_C([c,a])$$

但是我们发现这一波推导过后并没有什么用，直接算还是 $O(A^3)$ 的。只是可以进行一些剪枝？

• $\mu(a),\mu(b),\mu(c)$ 都必须非零，这样可以去掉很多无用的枚举；
• $\max\big\{[a,b],[b,c],[c,a]\big\}\le A$，好像也可以减掉一些枚举。

这些剪枝足够吗？如果仍然三重 for 循环枚举，这样剪枝过后还是过不了。但是注意到这两个限制，第二个限制与两个变量相关，类似于图上的边。

• 条件一限制了图上的点的 $\mu$ 非零；
• 条件二表示，若 $[a,b]\le A$，则图上存在 $(A,B)$ 这条无向边。

恰巧的是，我们计算的是一个三元组，体现在图上就是一个三元环！

记 $M$ 为图的边数，我们可以用下面的方法 $O(M\sqrt{M})$ 地枚举所有三元环：

• 统计每个点的度数，记作 $deg_u$；
• 给边定向，由度数大的点指向度数小的，若度数相等，则编号大的指向编号小的（编号小指向编号大也无所谓，反正要求二元组 $(\deg_u,u)$ 的大小比较唯一且具有传递性）；
• 枚举点 $u$：
  • 标记 $u$ 连出的所有点 $v$；
  • 枚举 $u$ 连出的点 $v$：
    • 枚举 $v$ 连出的点 $w$，若 $w$ 有标记，则找到三元环。

三元环计数正确性、时间复杂度的证明

根据边定向的规则，因为数对 $(deg_u, u)$ 的大小关系具有传递性且唯一确定，所以定向后的图一定是 DAG。

这意味着三元环一定是由 $u\to v\to w$ 和 $u\to w$ 构成的。且根据我们的枚举方式，这样的三元环仅能在枚举 $u$ 时计算到。所以计数不重不漏，正确性有保证。

时间复杂度的证明类似分块。首先，标记点的时间复杂度为 $O(M)$，因为每条边只会遍历一次，不是复杂度的瓶颈。

然后关注枚举的 $u\to v\to w$ 的中心点 $v$：

• 若 $deg_v\le\sqrt{M}$，则 $w$ 只有 $O(\sqrt{M})$ 个，$(u,v)$ 最多 $O(M)$ 个，则所有此类点 $v$ 的复杂度为 $O(M\sqrt{M})$；
• 若 $deg_v\gt\sqrt{M}$，因为 $u$ 连向 $v$，则 $deg_u\ge deg_v\gt\sqrt{M}$，这样的 $u$ 只有 $O(\sqrt{M})$ 个，而 $(v,w)$ 仅有 $O(M)$ 个；则所有此类 $v$ 点的复杂度也为 $O(M\sqrt{M})$。

总复杂度 $O(M\sqrt{M})$。

回到这道题上来，我们就是要枚举图上的一个三元环然后计算答案。那么这个图的边数多大呢？打个表发现 $O(M\sqrt{M})$ 能过……（反正我不会证）

于是按上述方法枚举即可。

注意实际上枚举的不止有三元环，还存在 $a=b$ 甚至是 $a=b=c$ 的情况，不过这两种都可以直接暴力枚举，不是很重要。

---

# 源代码

/*Lucky_Glass*/
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define con(typ) const typ &
typedef long long llong;
typedef pair<int, int> pii;

inline int rin(int &r) {
	int b = 1, c = getchar(); r = 0;
	while ( c < '0' || '9' < c ) b = c == '-' ? -1 : b, c = getchar();
	while ( '0' <= c && c <= '9' ) r = (r * 10) + (c ^ '0'), c = getchar();
	return r *= b;
}
inline void write(con(int) w) {
	if ( w > 9 ) write(w / 10), putchar((w % 10) ^ '0');
	else if ( w < 0 ) putchar('-'), write(-w);
	else putchar(w ^ '0');
}

const int N = 2e5 + 10, M = 2e6, MOD = 1e9 + 7;

inline int iGCD(con(int) a, con(int) b) {return b ? iGCD(b, a % b) : a;}

int na, nb, nc, ncas, nprm, nedg;
int mu[N], prm[N], deg[N], edg[M][3], tag[N];
llong fa[N], fb[N], fc[N];
bool vis[N];
vector<pii> lnk[N];

void init() {
	mu[1] = 1;
	for (int i = 2; i < N; i++) {
		if ( !vis[i] ) prm[++nprm] = i, mu[i] = -1;
		for (int j = 1; j <= nprm && prm[j] * i < N; j++) {
			vis[i * prm[j]] = true;
			if ( i % prm[j] == 0 ) break;
			mu[i * prm[j]] = -mu[i];
		}
	}
}
void proc(con(int) n, llong *arrf) {
	for (int i = 1; i <= n; i++) {
		arrf[i] = 0;
		for (int j = i; j <= n; j += i)
			arrf[i] += n / j;
	}
}
int main() {
	init();
	rin(ncas);
	while ( ncas-- ) {
		rin(na), rin(nb), rin(nc);
		int mx = max(na, max(nb, nc)), mn = min(na, min(nb, nc));
		fill(fa, fa + mx + 1, 0);
		fill(fb, fb + mx + 1, 0);
		fill(fc, fc + mx + 1, 0);
		proc(na, fa), proc(nb, fb), proc(nc, fc);
		llong ans = 0;
		// Part 1
		for (int i = 1; i <= mn; i++)
			ans += mu[i] * fa[i] * fb[i] * fc[i]; // mu[i] ^ 3 = mu[i]
		// Part 2
		fill(deg, deg + 1 + mx, 0), nedg = 0;
		for (int g = 1; g <= mx; g++)
			for (int i = 1; i * g <= mx; i++) if ( mu[i * g] )
				for (int j = i + 1; 1ll * i * j * g <= mx; j++)
					if ( mu[j * g] && iGCD(i, j) == 1 ) {
						int lcm = i * j * g, ig = i * g, jg = j * g;
						// iij
						ans += mu[jg] * (fa[ig] * fb[lcm] * fc[lcm]
							 + fa[lcm] * fb[ig] * fc[lcm]
							 + fa[lcm] * fb[lcm] * fc[ig]);
						// ijj
						ans += mu[ig] * (fa[jg] * fb[lcm] * fc[lcm]
							 + fa[lcm] * fb[jg] * fc[lcm]
							 + fa[lcm] * fb[lcm] * fc[jg]);
						// add edges at the same time :)
						deg[ig]++, deg[jg]++;
						edg[++nedg][0] = ig, edg[nedg][1] = jg;
						edg[nedg][2] = lcm;
					}
		// Part 3
		for (int i = 1; i <= mx; i++) lnk[i].clear();
		for (int i = 1; i <= nedg; i++)
			if ( deg[edg[i][0]] > deg[edg[i][1]]
			  || (deg[edg[i][0]] == deg[edg[i][1]] && edg[i][0] < edg[i][1]) )
				lnk[edg[i][0]].push_back(make_pair(edg[i][1], edg[i][2]));
			else lnk[edg[i][1]].push_back(make_pair(edg[i][0], edg[i][2]));
		for (int u = 1; u <= mx; u++) if ( mu[u] ) {
			for (int i = 0, ii = (int)lnk[u].size(); i < ii; i++)
				tag[lnk[u][i].first] = lnk[u][i].second;
			for (int i = 0, ii = (int)lnk[u].size(); i < ii; i++) {
				int v = lnk[u][i].first, luv = lnk[u][i].second;
				for (int j = 0, _j = (int)lnk[v].size(); j < _j; j++)
					if ( tag[lnk[v][j].first] ) {
						int w = lnk[v][j].first, lvw = lnk[v][j].second,
							luw = tag[w];
						ans += mu[u] * mu[v] * mu[w] * (
							fa[luv] * fb[luw] * fc[lvw]
						  + fa[luv] * fb[lvw] * fc[luw]
						  + fa[luw] * fb[luv] * fc[lvw]
						  + fa[luw] * fb[lvw] * fc[luv]
						  + fa[lvw] * fb[luv] * fc[luw]
						  + fa[lvw] * fb[luw] * fc[luv]
						);
					}
			}
			for (int i = 0, ii = (int)lnk[u].size(); i < ii; i++)
				tag[lnk[u][i].first] = 0;
		}
		write(int(ans % MOD)), putchar('\n');
	}
	return 0;
}

---

THE END

Thanks for reading!

怎知晓 有人 玩世不恭掩愁肠
取次花丛懒望 等剪烛西窗
怎知晓 有人 独为异客在异乡
嘴上逞强终不敢 举头看月光

——《从前有个衔玉教》By 星葵/鲜洋芋/溱绫西陌

> Link 【0412乐正绫诞生祭】从前有个衔玉教-Bilibili