自动搬运

查看原文

来自洛谷，原作者为

	emptysetvvvv 这里埋葬着一位 OIer 的青春

搬运于2025-08-24 21:46:00，当前版本为作者最后更新于2019-08-05 18:01:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

背景

小萌新 $\varnothing$ 如何也想不到，此题存在 $O(n)$ 的做法！！

思路

Part I

显然，总体思路应为：【三角形数量】等于【任选三个点的方案数】减去【三点共线的方案数】。

共有 $(n+1)(m+1)$ 个点，故【任选三个点的方案数】为 $C_{(n+1)(m+1)}^3$。

【三点共线的方案数】等于【横着的】加【竖着的】加【斜着的】。

【横着的】指三点所在直线平行于 $x$ 轴。共有 $m+1$ 条横线，每条横线上有 $n+1$ 个点，从这 $n+1$ 个点中选取 $3$ 个，方案数为 $(m+1)\cdot C_{n+1}^3$。

同理，【竖着的】指三点所在直线平行于 $y$ 轴，方案数为 $(n+1)\cdot C_{m+1}^3$。

看来，我们现在最关心的是【斜着的】，斜着的直线按斜率正负分为两种，并且这两种的方案数是相等的。因此，我们只需要计算出斜率为正的方案数，再乘以 $2$ 即可。

方便起见，不妨将核心计算内容——斜率为正的方案数记为 $ans$。

Part II

先考虑较朴素的 $O(n^2)$ 做法。

在此之前，观察可以发现一个小小的结论：

假设网格中 $AB$ 平行于底边 $x$ 轴，长度为 $i$ ，$BC$ 平行于侧边 $y$ 轴，长度为 $j$ ，那么 $AC$ 上的整点数量为 $\gcd(i,j)+1$。

那么我们可以枚举两点横坐标差 $i$，纵坐标差 $j$，则两点连线上的整点数量为 $\gcd(i,j)+1$（不算两端点自身的话有 $\gcd(i,j)-1$ 个）。

对于每组横坐标差 $i$，纵坐标差 $j$ 的点对，我们先选取两端点，再在他俩之间的 $\gcd(i,j)-1$ 个点中任选一个作为第三个点，方案数为 $\gcd(i,j)-1$。

每组点对可以有 $\gcd(i,j)-1$ 种方案，像这样横坐标差 $i$，纵坐标差 $j$ 的点对共有 $(n-i+1)(m-j+1)$ 个，故可以枚举 $i,j$ 计算：

$$ans=\sum_{i=1}^n\sum_{j=1}^m(n-i+1)(m-j+1)(\gcd(i,j)-1) $$

直接计算这个式子复杂度 $O(nm)=O(n^2)$，考虑 $\gcd$ 的计算的话甚至是 $O(n^2\log n)$。当然，对于本题的数据是绰绰有余了。

Part III

提供一个相当美妙并且相当好写的 $O(n)$ 做法。

我们看到 $[\gcd(i,j)=1]$ 这样的项时，总是按照莫比乌斯反演套路将其化为 $\sum_{d\mid\gcd(i,j)}\mu(d)$。

实际上，对于 $\gcd(i,j)$ 这样的项时，也是有套路的，那就是根据欧拉反演将其化为 $\sum_{d\mid\gcd(i,j)}\varphi(d)$。

他的原理是欧拉函数的一个有趣性质：

$n$ 的所有因子的欧拉函数和为 $n$ ，即 $\sum_{d\mid n}\varphi(d)=n$。

证明及更详细的信息见 $\varnothing$ 的博客。

也就是说：

$$ans=\sum_{i=1}^n\sum_{j=1}^{m}(n-i+1)(m-j+1)\left(\sum_{d\mid\gcd(i,j)}\varphi(d)-1\right) $$

考虑到 $\varphi(1)=1$，不妨先预先化简下，把 $\varphi(1)$ 和 $-1$ 抵消掉，免得以后麻烦：

$$ans=\sum_{i=1}^n\sum_{j=1}^{m}(n-i+1)(m-j+1)\sum_{d\mid\gcd(i,j)}^{d\ne 1}\varphi(d) $$

更复杂了？不妨先来看看 $d|\gcd(i,j)$ 的含义：

$i,j$ 的最大公约数的每个因子。

那不正是 $i,j$ 的每个公约数吗？

枚举 $i,j$ 再枚举他们的所有公约数，等价于枚举每个约数 $d$ 再枚举 $d$ 的 $i$ 倍、$j$倍。

可以看出，$d$ 的取值范围成了 $[2,\min(n,m)]$，$i,j$ 最小可取 $1$，最大分别取 $\left\lfloor\dfrac{n}{d}\right\rfloor,\left\lfloor\dfrac{m}{d}\right\rfloor$，即：

$$ans=\sum_{d=2}^{\min(n,m)}\sum_{i=1}^{\lfloor{n/d}\rfloor}\sum_{j=1}^{\lfloor{m/d}\rfloor}(n-id+1)(m-jd+1)\varphi(d) $$$$=\sum_{d=2}^{\min(n,m)}\varphi(d)\sum_{i=1}^{\lfloor{n/d}\rfloor}(n-id+1)\sum_{j=1}^{\lfloor{m/d}\rfloor}(m-jd+1) $$

很明显，$\sum_{i=1}^{\lfloor{n/d}\rfloor}(n-id+1)$ 是等差数列求和，

首项为 $(n-d+1)$，末项为 $(n-\left\lfloor\dfrac{n}{d}\right\rfloor d+1)$ 即 $(n\bmod d+1)$，项数为 $\left\lfloor\dfrac{n}{d}\right\rfloor$，故：

$$\sum_{i=1}^{\lfloor{n/d}\rfloor}(n-id+1)=\dfrac{1}{2}(n-d+1+n\bmod d+1)\left\lfloor\dfrac{n}{d}\right\rfloor $$

同理有：

$$\sum_{j=1}^{\lfloor{m/d}\rfloor}(m-jd+1)=\dfrac{1}{2}(n-d+1+n\bmod d+1)\left\lfloor\dfrac{n}{d}\right\rfloor $$

最终得到：

$$ans=\dfrac{1}{4}\sum_{d=2}^{\min(n,m)}\varphi(d)(n-d+n\bmod d+2)\left\lfloor\dfrac{n}{d}\right\rfloor(m-d+m\bmod d+2)\left\lfloor\dfrac{m}{d}\right\rfloor $$

欧拉函数可以利用欧拉筛线性预处理出，枚举 $d$ 复杂度 $O(\min(n,m))=O(n)$。

代码

#include <cstdio>
#include <iostream> 
using namespace std;
const int maxn = 1005;
int n, m, p[maxn], phi[maxn], tot;
bool mark[maxn];
long long ans;
long long C(long long x) { return x * (x-1) * (x-2) / 6; }
void sieve(int n) {
	phi[1] = 1;
	for(int i = 2; i <= n; ++i) {
		if(!mark[i]) p[++tot] = i, phi[i] = i - 1;
		for(int j = 1; j <= tot and p[j]*i <= n; ++j) {
			mark[p[j]*i] = true;
			if(i % p[j]) phi[p[j]*i] = phi[i] * (p[j]-1);
			else { phi[p[j]*i] = phi[i] * p[j]; break; }
		}
	}
}
int main() {
	scanf("%d %d", &n, &m);
	if(n > m) swap(n, m);
	sieve(n);
	for(int d = 2, x, y; d <= n; ++d)//记得 ans 要乘以 2，这里直接除以 2 就行了不用除以 4
		ans += (long long)phi[d]*(n-d+n%d+2)*(n/d)*(m-d+m%d+2)*(m/d)/2;
	ans = C((n+1)*(m+1)) - (m+1)*C(n+1) - (n+1)*C(m+1) - ans;
	printf("%lld\n", ans);
}

p.s

不考虑一些奇奇怪怪的 0ms 的话，$\varnothing$ 当初交的时候是 29ms 最优解诶。

觉得蛮有意思的话也请点个赞吧，无论你是否看明白了。