SDOI2015约数个数和

[SDOI2015]约数个数和

题目简述

求:

分析

证明:

所以说,可以有这样的假设:

  • 当 $x\perp y\;\;\land {a_k}^\prime>0$ 时,$x\times y$ 的 $p_k$ 的指数就是 ${a_k}^\prime$。
  • 当 $x\perp y\;\;\land {b_k}^\prime>0$ 时,$x\times y$ 的 $p_k$ 的指数就是 $a_k+{b_k}^\prime$

所以这样可以不重不漏的枚举出所有 $ij$ 的约数。

化简

所以原式可以化为:

所以就是 $O(n)$ 的预处理 $+\;O(T\sqrt n)$ 的查询,这道题就愉快的结束了。

Code