傳送門
設 $n=\prod_{i=1}^{m}p_{i}^{k_i}$
對每個質因子單獨考慮，如果 $a$ 的這個質因子 $p_i$ 的次數小于 $k_i$，那麼 $b$ 的這個質因子次數必須為 $k_i$
考慮 $a$ 這個質因子有多少種的取值，如果取 $p_{i}^{0}$ 到 $p_{i}^{k_i-1}$ 那麼 $b$ 都為 $p_{i}^{k_i}$
那麼這種情況對 $a$ 的貢獻就是 $\sum_{j=0}^{k_i-1}p_{i}^{j}$
如果 $a$ 取 $p_{i}^{k_i}$ ，那麼 $b$ 可以取 $p_{i}^{0}$ 到 $p_{i}^{k_i}$，一共有 $k_i+1$ 對
綜合一下，$a$ 的這個質因子可以取的總和為 $\sum_{j=0}^{k_i}p_{i}^{j}+k_{i} \cdot p_{i}^{k_i}$
因為 $a$ 是各個質因子乘起來的結果，是以根據乘法原理 $a$ 的所有取值的總和為 $\prod_{i=1}^{m}(\sum_{j=0}^{k_i}p_{i}^{j}+k_{i} \cdot p_{i}^{k_i})$
$b$ 也同理，然後發現這樣把 $a,b$ 看成了有序數對，除了 $(n,n)$ 以外都算了兩次，是以把和加上 $(n+n)$ 再除以 $2$ 就是答案了
$\sum_{j=0}^{k_i}p_{i}^{j}$ 就是個等比數列求和的式子，公式直接套就行了
注意是在模意義下，套式子的時候負數要轉正，除法要轉逆元