結果
問題 | No.1233 割り切れない気持ち |
ユーザー |
![]() |
提出日時 | 2019-07-31 00:37:48 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,833 ms / 3,153 ms |
コード長 | 1,326 bytes |
コンパイル時間 | 1,868 ms |
コンパイル使用メモリ | 180,812 KB |
実行使用メモリ | 25,344 KB |
最終ジャッジ日時 | 2024-06-22 19:11:25 |
合計ジャッジ時間 | 24,398 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 39 |
ソースコード
#include <bits/stdc++.h> int ri() { int n; scanf("%d", &n); return n; } int main() { int n = ri(); std::map<int, int> a; std::map<int, std::pair<int, int64_t> > sum; for (int i = 0; i < n; i++) a[ri()]++; std::pair<int, int64_t> cur = {0, 0}; for (auto &i : a) { sum[i.first] = cur; cur.first += i.second; cur.second += (int64_t) i.first * i.second; } int cache[401]; for (int i = 0; i <= 400; i++) cache[i] = -1; int64_t ans = 0; for (auto &i : a) { int64_t res = 0; if (i.first <= 400) { if (cache[i.first] == -1) { cache[i.first] = 0; for (auto &j : a) cache[i.first] += (j.first % i.first) * j.second; } res = cache[i.first]; } else { for (int j = 0; j < 200000; j += i.first) { auto low = sum.lower_bound(j); auto high = sum.lower_bound(j + i.first); int64_t xsum = (high == sum.end() ? cur.second : high->second.second) - (low == sum.end() ? cur.second : low->second.second); int num = (high == sum.end() ? cur.first : high->second.first) - (low == sum.end() ? cur.first : low->second.first); // std::cerr << xsum << " " << num * i.first * (j / i.first) << std::endl; res += xsum; res -= (int64_t) num * i.first * (j / i.first); } } res *= i.second; ans += res; } std::cout << ans << std::endl; return 0; }