Submission #75560059

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int ll

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

const int mod = 998244353;

int fix(int x){
    x%=mod;
    if(x<0)x+=mod;
    return x;
}

int modpow(int x, int y) {
    return !y?1:((y % 2 ? x : 1) * modpow((x * x) % mod, y / 2)) % mod;
}

int inverse(int x){
    return modpow(x,mod-2);
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    vector<int>a(n+1);
    vector<int>inv(n+1);
    for(int i = 1; i<=n; i++){
        inv[i] = inverse(i);
    }
    for(int i = 1; i<=n; i++){
        cin >> a[i];
    }
    vector<int>dp(n+1);
    vector<int>f(n+1);
    vector<vi>factors(n+1);
    for(int i = 1; i<=n; i++){
        for(int j = i; j<=n; j+=i){
            factors[j].push_back(i);
        }
    }
    dp[1] = 1;
    for(int nxt : factors[a[1]]){
        f[nxt] += dp[1] * a[1]; f[nxt] %= mod;
    }
    vector<int>arr(n+1);
    for(int i = 2; i<=n; i++){
        int v = a[i];
        for(int j = sz(factors[v]) - 1; j>=0; j--){
            int fac1 = factors[v][j];
            arr[fac1] = f[fac1];
            for(int k = j+1; k<sz(factors[v]); k++){
                int fac2 = factors[v][k];
                if(fac2 % fac1 == 0){
                    arr[fac1] = fix(arr[fac1] - arr[fac2]);
                }
            }
            dp[i] += arr[fac1] * inv[fac1] % mod;
            dp[i] %= mod;
        }
        
        dp[i] *= a[i]; dp[i] %= mod;
        for(int fac : factors[v]){
            arr[fac] = 0;
            f[fac] += dp[i] * a[i]; f[fac] %= mod;
        }
        cout << dp[i] << '\n';
    }
    return 0;
}

Submission Info

Judge Result