题解：CF2091E Interesting Ratio
Error_Eric
·
·
题解
Statement
求小于等于 n 的所有自然数组成的数对 (a,b) 中，\mathrm{lcm}(a,b)\over\gcd(a,b) 是质数的无序对的个数。
Solution
注意到 a=b 肯定不行，那么不妨令 a<b。
两个整数的乘积是质数只有一种情况：小的那个是 $1$。因此 ${a\over\gcd(a,b)} = 1$，也就是说 $a = \gcd(a, b), b= \mathrm{lcm}(a, b)$。
换言之 $(a,b)$ 合法当且仅当 $b\over a$ 是个质数。那么对于每个 $b$，合法的 $a$ 的和 $b$ 的质因数一一对应。
枚举 $b$ 可以得到答案就是 $d(i)$ 的前缀和，其中 $d(i)$ 表示 $i$ 的不同质因数个数。
$d$ 能够有很多方法处理。一个比较简单的做法是做个线性筛。每次用质数 $p$ 筛合数的时候，若合数的另外一个乘数 $q$ 不是 $p$ 的倍数，则 $d(pq) = d(q)+1$。否则 $d(pq) = d(q)$。答案输出 $d$ 的前缀和即可。
### Code
[Link](https://vjudge.net/solution/59511618)