## 题目描述定义函数 $fn = displaystylesum_i = 1^n sum_j = 1^n sum_k = 1^n i + j + k = n operatornamelcmi gcdj k$给定 $n$对于所有 $1 leq i leq n$求出所有 $fi bmod 998244353$ 的值。## 输入格式一行一个整数 $n$。## 输出格式一行$n$ 个整数表示所有 $fi

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, M = 998244353;
int n, f[N], g[N], ans[N], phi[N], p[N], cnt, mu[N], vis[N];
void init() {
    phi[1] = mu[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            p[++cnt] = i;
            phi[i] = i - 1;
            mu[i] = M - 1;
        }
        for (int j = 1; j <= cnt && p[j] * i <= n; j++) {
            vis[p[j] * i] = 1;
            if (i % p[j] == 0) {
                phi[p[j] * i] = phi[i] * p[j];
                break;
            }
            phi[p[j] * i] = phi[i] * (p[j] - 1);
            mu[p[j] * i] = (M - mu[i]) % M;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j += i) {
            g[j] = (g[j] + 1ll * phi[j / i] * i) % M;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j += i) {
            f[j] = (f[j] + 1ll * mu[j / i] * g[i]) % M;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j += i) {
            ans[j] = (ans[j] + 1ll * f[i] * (j / i)) % M;
        }
    }
}
int main() {
    scanf("%d", &n);
    init();
    for (int i = 1; i <= n; i++) {
        printf("%d ", ans[i]);
    }
    return 0;
}
``