Submission #7641462

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define int long long
using namespace std;
typedef pair<int, int> P;
const int mod = 998244353;
const int MAX = 1000000;

long long mod_pow(long long x, long long n){
    if(n == 0) return 1;
    long long res = mod_pow(x*x % mod, n / 2);
    if(n & 1) res = res*x % mod;
    return res;
}

int sum[MAX + 1];
int sum2[MAX + 1];

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    rep(i, 0, n){
        int in;
        cin >> in;
        (sum[in] += in) %= mod;
        (sum2[in] += in * in) %= mod;
    }
    for(int i = 1; i <= MAX; i++){
        for(int j = 2 * i; j <= MAX; j += i){
            (sum[i] += sum[j]) %= mod;
            (sum2[i] += sum2[j]) %= mod;
        }
    }
    for(int i = 1; i <= MAX; i++){
        sum[i] = sum[i] * sum[i] % mod;
    }
    for(int i = MAX; i >= 1; i--){
        for(int j = 2 * i; j <= MAX; j += i){
            (sum[i] = sum[i] - sum[j] + mod) %= mod;
            (sum2[i] = sum2[i] - sum2[j] + mod) %= mod;
        }
    }
    int ans = 0;
    for(int i = 1; i <= MAX; i++){
        int tmp = (sum[i] - sum2[i] + mod) % mod;
        tmp = tmp * mod_pow(2, mod - 2) % mod;
        tmp = tmp * mod_pow(i, mod - 2) % mod;
        ans += tmp;
        ans %= mod;
    }
    cout << ans << endl;
}

Submission Info

Judge Result