题目描述
-
给定一个长度为 \(N\) 的数列 \(A_1, A_2, A_3, \ldots, A_N\)。
-
请你求出 \(\sum_{i=1}^{N}\sum_{j=i+1}^{N}\mathrm{lcm}(A_i,A_j)\) 的值模 \(998244353\) 的结果。
-
\(1 \leq N \leq 2 \times 10^5\)，\(1 \leq A_i \leq 10^6\)。
-
$ 1\ \leq\ N\ \leq\ 200000 $
-
$ 1\ \leq\ A_i\ \leq\ 1000000 $
思路点拨
这种题目还是很好想到莫比乌斯反演的。我们对于序列中的每一个数记录出现的次数 \(cnt_i\) ，这就是指 \(i\) 在 \(A\) 的出现次数。