最大公约数 Coca cola espuma 🥤

思路

求所有 $g c d (x, y) = p$ ，且p为素数的数对个数。

已知，当条件成立时有 $g c d (\frac{x}{p}, \frac{y}{p}) = 1$ ，令 $x^{'} = \frac{x}{p}, y^{'} = \frac{y}{p}$ ，确定质数 p 后， $x, y$ 的个数也是 $x^{'}, y^{'}$ 的个数。

而其满足 $1 \leq x^{'}, y^{'} \leq \frac{N}{p}$ ，又由 $g c d (x^{'}, y^{'}) = 1$ 表示 $x^{'}, y^{'}$ 互质，那么就是求 $[1, \frac{N}{p}]$ 中互质的 $x^{'}, y^{'}$ 个数。

像可见的点一题类似，可以枚举 x 的值，来求 $1 + 2 \times i = 1 \sum \frac{N}{p} φ (x_{i})$ ，就是 $[1, \frac{N}{p}]$ 的互质数对个数。

因为 $\frac{N}{p}$ 的值不同，故用前缀和处理 $s [i] = \sum φ (i)$ ，便于查询。

最终结果就是 $2 \times s [N / p]$ ，令 $φ (1) = 0$ 之后就不用再把结果+1。