纪念第一次场切 ARC E。

对于每个 $1 \le m \le n$，我们把求和式给写下来：

$$\sum_{S \notin \empty, S \in \{1, 2, \ldots, n\}}\sum_{i = 1} ^ {|S| - 1}\gcd(A_{S_i}, A_{S_{i + 1}})$$

直接枚举是 $O(2^n\times n)$ 的，考虑计算每对 $(i, j)$ 对答案的贡献，那么转换为：

$$\sum_{i = 1} ^ n \sum_{j = i + 1} ^ n\gcd(i, j)f(i, j)$$

$f(i, j)$ 即为 $2^{n - j} \times 2 ^{i - 1}$，因为 $1 \sim i - 1$ 随便选，$j + 1 \sim n$ 同理，因此这个式子成立。

接下来就开始大力推式子了：

$$\begin{aligned} \sum_{i = 1} ^ n \sum_{j = i + 1} ^ n\gcd(i, j)f(i, j) &= \sum_{i = 1} ^ n \sum_{j = i + 1} ^ n\gcd(i, j)2^{i - 1}2^{n - j} \\ &= \sum_{i = 1}^n\sum_{j = i + 1}^n2^{i - 1}2^{n - j}\sum_{d \mid A_i, d \mid A_j} \varphi(d) \\ &= \sum_{d = 1} ^ D\varphi(d)\sum_{1 \le i < j \le n, d \mid a_i, d \mid a_j}2^{i - 1}2^{n - j} \\ &= \sum_{d = 1}^ D \varphi(d)\sum_{i = 1}^n[d \mid a_i]2^{i - 1}\sum_{j = i + 1}^n[d \mid a_j]2^{n - j} \\ &= \sum_{d = 1}^D \varphi(d)\sum_{i = 1}^n[d \mid a_i]2^{n + i - 1}\sum_{j = i + 1}^n[d \mid a_j]2^{-j} \end{aligned}$$

做一波前缀和即可。

时间复杂度 $O(n + V \log V + \sum d_{a_i})$。

参考代码如下：

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int mx = 1e5 + 6, P = 998244353;
int n, a[500006];
int phi[mx], vis[mx], pr[mx], tot;
int pw[500006], pw_inv[500006]; 
int s[500006], sd[mx];
int pre[500006];
int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  phi[1] = 1;
  for (int i = 2; i < mx; ++i) {
    if (!vis[i]) {
      pr[++tot] = i;
      phi[i] = i - 1;
    }
    for (int j = 1; j <= tot && i * pr[j] < mx; ++j) {
      vis[i * pr[j]] = 1;
      if (i % pr[j] == 0) {
        phi[i * pr[j]] = phi[i] * pr[j];
        break;
      }
      phi[i * pr[j]] = phi[i] * (pr[j] - 1);
    }
  }
  vector<vector<int>> divs(mx);
  for (int i = 1; i < mx; ++i) {
    for (int j = i; j < mx; j += i) {
      divs[j].emplace_back(i);
    }
  }
  int inv2 = (P + 1) / 2;
  pw[0] = pw_inv[0] = 1;
  for (int i = 1; i <= n; ++i) {
    pw[i] = pw[i - 1] * 2 % P;
    pw_inv[i] = pw_inv[i - 1] * inv2 % P;
  }
  for (int i = 1; i <= n; ++i) {
    for (auto v : divs[a[i]]) {
      s[i] += phi[v] * sd[v] % P;
      s[i] %= P;
    }
    for (auto v : divs[a[i]]) {
      sd[v] = (sd[v] + pw[i - 1]) % P;
    }
  }
  for (int i = 1; i <= n; ++i) {
    pre[i] = (pre[i - 1] + s[i] * pw_inv[i] % P) % P;
  }
  for (int i = 1; i <= n; ++i) {
    cout << pre[i] * pw[i] % P << '\n';
  }
}