#790477 (C++14) No.2046 Ans Mod? Mod Ans!

• 問題: No.2046 Ans Mod? Mod Ans!
• ユーザー: QCFium
• 提出日時: 2022-08-19 22:39:02
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 347 ms / 4,000 ms
• コード長: 1,198 bytes
• コンパイル時間: 1,839 ms
• コンパイル使用メモリ: 175,000 KB
• 実行使用メモリ: 6,736 KB
• 最終ジャッジ日時: 2023-08-22 11:45:06
• 合計ジャッジ時間: 3,829 ms
• ジャッジサーバーID （参考情報）: judge14 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	3 ms; 5,832 KB
testcase_01	AC	3 ms; 5,732 KB
testcase_02	AC	3 ms; 5,776 KB
testcase_03	AC	6 ms; 5,788 KB
testcase_04	AC	5 ms; 5,760 KB
testcase_05	AC	6 ms; 5,784 KB
testcase_06	AC	5 ms; 5,816 KB
testcase_07	AC	5 ms; 5,900 KB
testcase_08	AC	4 ms; 5,752 KB
testcase_09	AC	4 ms; 5,768 KB
testcase_10	AC	5 ms; 5,772 KB
testcase_11	AC	6 ms; 5,748 KB
testcase_12	AC	4 ms; 5,812 KB
testcase_13	AC	68 ms; 6,128 KB
testcase_14	AC	44 ms; 5,972 KB
testcase_15	AC	111 ms; 6,364 KB
testcase_16	AC	117 ms; 6,244 KB
testcase_17	AC	91 ms; 6,420 KB
testcase_18	AC	177 ms; 6,288 KB
testcase_19	AC	96 ms; 6,248 KB
testcase_20	AC	347 ms; 6,736 KB

ソースコード

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

int main() {
	int n = ri();
	int a[n];
	for (auto &i : a) i = ri();
	std::sort(a, a + n);
	
#	define MAX 200000
	int sum[MAX + 2];
	memset(sum, 0, sizeof(sum));
	for (auto i : a) sum[i + 1]++;
	for (int i = 0; i <= MAX; i++) sum[i + 1] += sum[i];
	
	int64_t sum2[MAX + 2];
	memset(sum2, 0, sizeof(sum2));
	for (auto i : a) sum2[i + 1] += i;
	for (int i = 0; i <= MAX; i++) sum2[i + 1] += sum2[i];
	
	std::map<int, int64_t> cache;
	int64_t res = 0;
	for (int i = n; i--; ) {
		int64_t cur = 0;
		if (a[i] <= 500) {
			if (!cache.count(a[i])) {
				for (int j = i + 1; j < n; j++) cur += a[j] % a[i];
				cache[a[i]] = cur;
			} else cur = cache[a[i]];
		} else {
			for (int j = 1; a[i] * j <= MAX; j++) {
				int left = a[i] * j;
				int right = std::min(MAX + 1, a[i] * (j + 1));
				cur += (sum2[right] - sum2[left]) - (int64_t) left * (sum[right] - sum[left]);
			}
		}
		int ok_cnt = sum[MAX + 1] - sum[a[i] + 1];
		res += (int64_t) ok_cnt * a[i] - cur;
		// std::cerr << (int64_t) ok_cnt * a[i] - cur << std::endl;
		// std::cerr << a[i] << " " << cur << std::endl;
	}
	std::cout << res << std::endl;
	
	return 0;
}