AGC 038 C - LCMs

Before solving this task, solve this problem.

\begin{align}
f_k = \sum_{\mathrm{gcd}(i, j)=k} a_i b_j.
\end{align}

We can find this from the following by inclusion-exclusion principle.

\begin{align}
F_k = \sum_{k \mid i \land k \mid j} a_i b_j.
\end{align}

That is, the common divisor is easier than the greatest common divisor. First, this holds.

\begin{align}
F_k = f_k + f_{2k} + f_{3k} + f_{4k} + \cdots
\end{align}

$F_k$ can be decomposed into two factors.

\begin{align}
F_k = \sum_{k \mid i \land k \mid j} a_i b_j = \left(\sum_{k \mid i} a_i\right) \left(\sum_{k \mid j} b_j\right).
\end{align}

We now have $F_1, F_2, F_3, \ldots$. Last, we reduce them into $f_1, f_2, f_3, \ldots$ by inclusion-exclusion. The formula is this.

\begin{align}
f[k] = F[k] - F[2k] - F[3k] - F[5k] + F[6k] + F[10k] + F[15k] - \cdots
\end{align}

Precisely,

\begin{align}
f[k] = F[k] - \sum_{p} F[pk] + \sum_{p \lt q} F[pqk] - \sum_{p \lt q \lt r} F[pqrk] + \cdots.
\end{align}

If we use moebius function, we obtain another expression.

\begin{align}
f[k] = \sum_{k \mid i} \mu\left( \frac{i}{k} \right)F[i].
\end{align}

Source Code

#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define range(a) a.begin(), a.end()

using namespace std;
using ll = long long;

constexpr int MOD = 998244353;

class mint {
int n;
public:
mint(int n_ = 0) : n(n_) {}
explicit operator int() { return n; }
friend mint operator-(mint a) { return -a.n + MOD * (a.n != 0); }
friend mint operator+(mint a, mint b) { int x = a.n + b.n; return x - (x >= MOD) * MOD; }
friend mint operator-(mint a, mint b) { int x = a.n - b.n; return x + (x < 0) * MOD; }
friend mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
friend mint &operator+=(mint &a, mint b) { return a = a + b; }
friend mint &operator-=(mint &a, mint b) { return a = a - b; }
friend mint &operator*=(mint &a, mint b) { return a = a * b; }
friend bool operator==(mint a, mint b) { return a.n == b.n; }
friend bool operator!=(mint a, mint b) { return a.n != b.n; }
friend istream &operator>>(istream &i, mint &a) { return i >> a.n; }
friend ostream &operator<<(ostream &o, mint a) { return o << a.n; }
};
mint operator "" _m(unsigned long long n) { return n; }

// c[gcd(i, j)] += a[i] * b[j]
vector<mint> zeta(vector<mint> f) {
const int n = f.size();
for (int i = 1; i < n; i++) {
for (int j = i * 2; j < n; j += i) {
f[i] += f[j];
}
}
return f;
}

vector<mint> moebius(vector<mint> f) {
const int n = f.size();
for (int i = n - 1; i >= 1; i--) {
for (int j = i * 2; j < n; j += i) {
f[i] -= f[j];
}
}
return f;
}

int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
constexpr int U = 1e6;
vector<mint> inv(U + 1);
inv[1] = 1;
for (int i = 2; i <= U; i++) {
inv[i] = inv[MOD % i] * (MOD - MOD / i);
}
int N; cin >> N;
vector<mint> f(U + 1);
vector<int> A(N);
rep(i, N) {
cin >> A[i];
f[A[i]] += A[i];
}
f = zeta(f);
for (int i = 1; i <= U; i++) {
f[i] *= f[i];
}
f = moebius(f);
mint ans = 0;
for (int i = 1; i <= U; i++) {
ans += f[i] * inv[i];
}
rep(i, N) {
ans -= mint(A[i]);
}
ans *= inv[2];
cout << ans << endl;
}