GMOI R1 T3 Solution

yinhy09 · 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 以内的质数全部预处理出来，就可以快速判断了。