結果
問題 | No.3054 Modulo Inequalities |
ユーザー |
|
提出日時 | 2025-01-18 16:16:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 194 ms / 2,500 ms |
コード長 | 1,255 bytes |
コンパイル時間 | 987 ms |
コンパイル使用メモリ | 74,380 KB |
実行使用メモリ | 12,032 KB |
最終ジャッジ日時 | 2025-02-02 13:29:14 |
合計ジャッジ時間 | 7,434 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 31 |
ソースコード
// correct #include <iostream> #include <vector> constexpr int M = 1000010; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; std::vector<long long> w(M + 1); for (int i = 0; i < n; ++i) { int a, b; std::cin >> a >> b; ++w[a + 1]; --w[b + 1]; if (const int d = a - b; d < 0) { --w[0]; --w[1]; ++w[-d]; } else { --w[d + 1]; } } // accumulate for (int i = 0; i < M; ++i) { w[i + 1] += w[i]; } // zeta transform { std::vector<int8_t> is_prime(M + 1, true); for (int p = 2; p <= M; ++p) { if (not is_prime[p]) continue; int q = M / p; for (; q >= p; --q) { is_prime[p * q] = false; w[q] += w[p * q]; } for (; q >= 1; --q) { w[q] += w[p * q]; } } } int max_f = -1, argmax = 0; for (int m = 1; m <= M; ++m) { const int f_m = 1LL * -n * (M / m) - w[0] - w[m]; if (f_m > max_f) { max_f = f_m; argmax = m; } } std::cout << argmax << '\n'; }