自动搬运

查看原文

来自洛谷，原作者为

	Petit_Souris 鼓励的话语 无论多少次我都会说给你听 | 你在名为弱小的深渊 究竟看见过什么 | 天空中出现了一种罕见的天文现象

搬运于2025-08-24 22:58:56，当前版本为作者最后更新于2024-05-21 21:09:59，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一分钟脑筋急转弯，建议早上起床看一眼检验精神状态。

考察组合意义。对于每组 $(i,j)$，$\lfloor\frac{n}{\max(i,j)}\rfloor\times [\gcd(i,j)=1]$ 实际上在统计满足以下条件的数对 $(x,y)$：

• $1\le x,y\le n$。

• 设 $g=\gcd(x,y)$，则 $(\frac{x}{g},\frac{y}{g})=(i,j)$。

不难发现每组 $(x,y)$ 都对应了唯一的一组 $(i,j)=(\frac{x}{g},\frac{y}{g})$，因此每个 $(x,y)$ 都被计算恰好一次，答案即为这样的二元组数量 $n^2$。