AGC 038 C - LCMs

https://atcoder.jp/contests/agc038/tasks/agc038_c

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;
}