$\text{Description}$
给定序列 $\{A\}$，计算：
$1\le n\le 2\times 10^5,A_i\le 10^6$。
$\text{Solution}$
对于这类序列上的数论问题，常见操作是通过桶把它转成自然数上的问题。
为了方便，我们将原式化为：
这样仅需考虑前面那一坨东西。
记 $t_i=\sum[A_j=i]$，则可化为：
化为 $\gcd$，可得：
枚举它：
消去后面 $d$ 的影响：
莫比乌斯反演：
交换求和次序：
不妨枚举 $kd$：
记：
化简得：
我们知道：
是个积性函数，可以线性筛筛出 $k\mu(k)$ 后狄利克雷卷积，所以我们可以直接线性算了……
当然也可以直接考虑它在素数幂处的取值，也就是 $f(1)=1,f(p^k)=1-p$。
$\text{Code}$
1 |