Contest Duration: - (local time) (110 minutes) Back to Home

Submission #7644098

Source Code Expand

Copy
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const ll MOD = 998244353;

// Linear sieve that additionally precalculates some common multiplicative functions
struct Sieve {
vector<int> primes;  // primes[i]    := i+1'th prime
vector<int> div_ind; // div_ind[x]   := minimum i s.t. primes[i] \divides x
vector<int> mobius;  // mobius[p^k]  := [k == 0] - [k == 1]

Sieve(int n) : div_ind(n+1, -1), mobius(n+1, 1) {
vector<int> base(n+1, 1);
for (int i = 2; i <= n; ++i) {
if (div_ind[i] == -1) {
div_ind[i] = primes.size();
primes.push_back(i);
}
for (int j = 0; j <= div_ind[i]; ++j) {
int p = primes[j];
int t = p * i;
if (t > n) break;
div_ind[t] = j;
base[t] = (j == div_ind[i] ? base[i] : i);
}

// Calculate multiplicative functions
int bs = base[i];
if (bs == 1) {
int p = primes[div_ind[i]];
int j = i/p;
mobius[i]  = (i == p ? -1 : 0);
} else {
int pk = i/bs;
mobius[i]  = mobius[bs]  * mobius[pk];
}
}
}
};

ll modInv(ll a, ll b = MOD - 2) {
if (b & 1) return a * modInv(a, b-1) % MOD;
if (b == 0) return 1;
return modInv(a*a % MOD, b / 2);
}

const int N = 1 + (int)1e6;
ll mdi[N];
ll cou[N];
ll sum[N];
ll aux[N];

int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);

for (int i = 1; i < N; ++i) mdi[i] = modInv(i);
Sieve sv(N);

for (int t = 1; t < N; ++t) {
for (int m = 1; m*t < N; ++m) aux[t*m] += mdi[t] * sv.mobius[m];
aux[t] %= MOD;
if (aux[t] < 0) aux[t] += MOD;
}

int n;
cin >> n;
for (int i = 0; i < n; ++i) {
int a;
cin >> a;
++cou[a];
}
for (int t = 1; t < N; ++t) {
for (int r = t; r < N; r += t) sum[t] += (ll)cou[r] * r;
sum[t] %= MOD;
}

ll res = 0;
for (int t = 1; t < N; ++t) {
ll mult = (sum[t] * sum[t]) % MOD;
res += (aux[t] * mult) % MOD;
}
for (int d = 1; d < N; ++d) {
res -= (ll)cou[d] * d % MOD;
}
res = ((res%MOD) * mdi[2]) % MOD;
if (res < 0) res += MOD;
cout << res << '\n';

// \sum_{a} \sum_{b} lca(a, b);
// = \sum_{a} \sum_{b} ab / gcd(a, b)
// = \sum_{a} \sum_{b} \sum_{k} [gcd(a, b) == k] ab / k
// = \sum_{k} 1/k \sum_{a} \sum_{b} ab [gcd(a, b) == k]
// = \sum_{k} 1/k \sum_{a} \sum_{b} ab \sum_{d | gcd(a, b)/k} mob(d)
// = \sum_{k} \sum_{d} 1/k mob(d) \sum_{dk | a} \sum_{dk | b} ab
// = \sum_{t} (\sum_{k | t} 1/k mob(t/k)) (\sum_{t | a} a)^2
// = \sum_{t} aux[t] sum[t]
}



#### Submission Info

Submission Time 2019-09-21 22:48:09+0900 C - LCMs mangolassi C++14 (GCC 5.4.1) 700 2515 Byte AC 357 ms 39732 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 332 ms 33588 KB
01-02.txt AC 343 ms 39732 KB
01-03.txt AC 348 ms 39732 KB
01-04.txt AC 333 ms 39732 KB
01-05.txt AC 346 ms 39732 KB
01-06.txt AC 344 ms 39732 KB
01-07.txt AC 339 ms 39732 KB
01-08.txt AC 346 ms 39732 KB
01-09.txt AC 342 ms 39732 KB
01-10.txt AC 353 ms 39732 KB
01-11.txt AC 351 ms 39732 KB
01-12.txt AC 354 ms 39732 KB
01-13.txt AC 355 ms 39732 KB
01-14.txt AC 357 ms 39732 KB
01-15.txt AC 352 ms 39732 KB
01-16.txt AC 350 ms 39732 KB
01-17.txt AC 351 ms 39732 KB
01-18.txt AC 348 ms 33588 KB
sample-01.txt AC 333 ms 33588 KB
sample-02.txt AC 332 ms 33588 KB
sample-03.txt AC 333 ms 39732 KB