rt，这题可以使用类似 P9118 [春季测试 2023] 幂次 的做法枚举 $\gcd$ 并直接计算这种情况的方案数做到 $O(n\log V)$，和其它方法复杂度相同而难度较低。