Submission #7641462


Source Code Expand

Copy
#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

Submission Time
Task C - LCMs
User treeone
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1411 Byte
Status AC
Exec Time 712 ms
Memory 16000 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 3
AC × 21
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt
All 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt AC 640 ms 13824 KB
01-02.txt AC 658 ms 15872 KB
01-03.txt AC 662 ms 15872 KB
01-04.txt AC 648 ms 15872 KB
01-05.txt AC 660 ms 15872 KB
01-06.txt AC 654 ms 15872 KB
01-07.txt AC 657 ms 15872 KB
01-08.txt AC 681 ms 15872 KB
01-09.txt AC 669 ms 16000 KB
01-10.txt AC 696 ms 15872 KB
01-11.txt AC 712 ms 15872 KB
01-12.txt AC 680 ms 15872 KB
01-13.txt AC 684 ms 15872 KB
01-14.txt AC 706 ms 15872 KB
01-15.txt AC 688 ms 15872 KB
01-16.txt AC 707 ms 15872 KB
01-17.txt AC 676 ms 15872 KB
01-18.txt AC 658 ms 13824 KB
sample-01.txt AC 640 ms 13824 KB
sample-02.txt AC 638 ms 13824 KB
sample-03.txt AC 652 ms 15872 KB