結果

問題 No.3054 Modulo Inequalities
コンテスト
ユーザー suisen
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 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';
}
0