P10532 [XJTUPC2024] 筛法

Description

题目传送门：P10532 [XJTUPC2024] 筛法

求：

$$\sum\limits_{i=1}^n\sum\limits_{j=1}^n\lfloor \dfrac{n}{\max(i,j)}\rfloor [i \perp j]$$

显然发现答案为 $n^2$。

Analysis（转自讲评视频）

我们可以从几何的角度出发:

考虑二维平面的 $n^2$ 个点 $(i,j)\ 1\le i,j\le n$。

从原点向每个满足 $i\perp j$ 的点 $(i,j)$ 引出一条射线，可以发现这 $n^2$ 个点均唯一存在于其中一条射线上，应为当 $\gcd(i,j)\not=1$ 时，$(i,j)$ 会被 $(\frac{i}{\gcd{(i,j)}},\frac{j}{\gcd{(i,j)}})$ 引出的射线覆盖。

我们再对每个 $i\perp j$ 的点对 $(i,j)$ 考虑其引出射线覆盖的点数，不难发现恰好就是 $\frac{n}{\max{(i,j)}}$，因为对所有 $1\le k\le \frac{n}{\max{(i,j)}}$，点对 $(ik,jk)$ 在这条射线上，当 $k$ 再大时 $ik,jk$ 中至少有一维超过 $n$。

故

$$\sum_{i=1}^{n}\sum_{j=1}^{n}[i\perp j][\frac{n}{\max{(i,j)}}]$$

可以理解为对所有互质的 $(i,j)$ 求上述射线所覆盖的点对数量，在上述结论中可知该和为 ${n}^{2}$。

还有几种解法不说了，可以自行去看讲评回放。

Code

x = int(input())
print(x * x)