数论

Problem ?

给定排列 $a_n$, 求 $\sum_i \sum_j gcd(i, j)gcd(a_i, a_j)$

$n\le 10^5$

$$
\begin{gathered}
\sum_i \sum_j gcd(i, j)gcd(a_i, a_j)\
=\sum_i \sum_j \sum_{d|i, j} \varphi(d) \sum_{k|a_i, a_j} \varphi(k)\
=\sum_d \varphi(d) \sum_k \varphi(k) (\sum_{d\vert i}[k\vert a_i])^2
\end{gathered}
$$

设 $g(d, k)=\sum_{d\vert i}[k\vert a_i]$

考虑一个 $(i, a_i)$ 对的贡献, 那么发现 $g$ 一共是 $\sum d(i) d(a_i)$, 又因为是排列, 于是这个就是 $\sum_i d^2(i)$, 据说是 $n\log^3 n$ 的.

那么你只枚举 $g$ 有值的 $i, j$ 就能做3log了. 简单想法是哈希表, 空间爆炸.

考虑逐个 $i$ 处理, 即固定一个 $i$, 枚举 $i$ 和 $a_i$ 的因数就行了.