题解：P10532 [XJTUPC2024] 筛法

Petit_Souris · 2024-05-21 21:09:59 · 题解

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

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

• 设 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。