其实我很想吐槽这题

我比赛的时候疯狂$\text{WA on test 16}​$

然后死活找不出来哪儿错了

我觉得我数组开小了

于是我开到$MLE$都没有过掉

最后一看

被一个n = 2的点卡掉了……

才出4题，罚时爆炸，上黄失败，掉分哭唧唧

第一篇题解

我们都知道$lcm(a, b) = \frac{a * b}{\gcd(a, b)}$

∴ $\frac{lcm(a, b)}{a} = \frac{\frac{a * b}{\gcd(a, b)}}{a} = \frac{b}{\gcd(a, b)}$

题目的意思就被我们转化成了求$\frac{b}{\gcd(a, b)}$的种类数

又∵b是一个确定的数

∴$\frac{b}{\gcd(a, b)}$的种类数就等于$\gcd(a, b)$的种类数

由于$a$的范围在$[1, 10^{18}]$范围内，所以$\gcd(a, b)$的种类数就等于b的因数个数。

因数个数就可以$O(\sqrt n)$求辣QwQ