自动搬运

查看原文

来自洛谷，原作者为

	yinhy09 既然选择了远方，便只顾风雨兼程~

搬运于2025-08-24 22:43:49，当前版本为作者最后更新于2022-12-15 22:22:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

官方题解

令 $\gcd(x,y)=d$ 且 $x=d \times x_{1},y=d \times y_{1}$，且 $\gcd(x_{1},y_{1})=1$。

可算得 $\operatorname{lcm}(x,y)=d \times x_{1} \times y_{1}$。

故原式化简为：$k \times d=d \times x_{1} \times y_{1}$ 约去 $d$，变为 $k=x_{1} \times y_{1}$ 且 $\gcd(x_{1},y_{1})=1$。

由算术基本定理，设 $k$ 中含有 $n$ 个不同的质因子。则可设：$k=a_{1}^{\alpha_{1}} \times a_{2}^{\alpha_{2}} \cdots \times a_{n}^{\alpha_{n}}$，其中 $a_{1},a_{2} \cdots a_{n} \in \operatorname{Prime}$。

若想将 $k$ 拆为两个互质的数相乘，则对于 $\forall i \in [1,n]$，若 $a_{i} \mid x_{1}$ 则有 $a_{i} \nmid y_{1}$。

故对于 $\forall i \in[1,n]$，$a_{i}$ 可以为 $x_{1}$ 或 $y_{1}$ 的因数。所以总情况数为 $2^n$ 种。

然而这 $n$ 种是在 $d$ 唯一确定的时候，然而原题目要求仅是 $P \le d \le Q$，所以 $d$ 还有 $Q-P+1$ 中取值，故答案为 $2^n\times(Q-P+1) \pmod {10^9+7}$。

那么此时，唯一的难点就变成了求 $n$ 的值。那么我们就需要采取试除的办法，每找到一个新的质因子就把计数器 $cnt++$，最终返回 $cnt$ 即可。

但是如果每一次都判断质数会非常的慢，所以我们采用线性筛将 $10^8$ 以内的质数全部预处理出来，就可以快速判断了。