思路:
由唯一分解定理, 可将两数$x, y$分解为:
若$a_x$对$b_y$有贡献, 则说明$\forall k, \alpha_{y,k} \ge \alpha_{x,k}$
相当于$b$是$a$的一个以质因子指数为维度的高维前缀和.
关于如何求高维前缀和, 可以用容斥, 但是这里使用了另一个方法: 求出前$n$维的前缀和后延新的维度推进求出$n+1$维前缀和.
以二维前缀和理解的话, 相当于先求出当前行的一维前缀和, 再延列推进求出二维前缀和.
时间复杂度与埃拉托色尼筛相当, 为$O(n \log \log n)$
代码:
1 |
|