# AtCoder AGC038 C-LCMs 题解

AC代码

#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include
#define SIZE 1000100
#define rep(i, a, b) for (long long i = a; i <= b; ++i)
#define int long long
using namespace std;
void io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
const int mod = 998244353;
int n, inv[SIZE] = { 0,1 }, cnt[SIZE], tp, maxx = 0, ans[SIZE], res = 0;
signed main() {
io(); cin >> n;
rep(i, 1, n) {
cin >> tp;
cnt[tp]++;
maxx = max(maxx, tp);
}
rep(i, 2, maxx) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
for (int i = maxx; i; --i) {    //求出gcd为i的所有pair的乘积之和
int s1 = 0, s2 = 0;
for (int j = i; j <= maxx; j += i) {
s1 = (s1 + cnt[j] * j % mod) % mod;
s2 = (s2 + cnt[j] * j % mod * j % mod) % mod;
}
ans[i] = (s1 * s1 % mod - s2 + mod) % mod;
// s1 - s2 的作用是使得gcd为j的pair对数为 cnt * (cnt - 1)
for (int j = i + i; j <= maxx; j += i) {
ans[i] = (ans[i] - ans[j] + mod) % mod;
//去重，删除gcd为ik (k > 1)的pair
}
}
rep(i, 1, maxx) {   //计算 ans[i] / i % mod
res = (res + ans[i] * inv[i] % mod) % mod;
}
cout << res * inv[2] % mod; //枚举了两遍gcd，res / 2
}