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
Task C - LCMs
User mangolassi
Language C++14 (GCC 5.4.1)
Score 700
Code Size 2515 Byte
Status AC
Exec Time 357 ms
Memory 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