結果

問題 No.3054 Modulo Inequalities
コンテスト
ユーザー suisen
提出日時 2025-01-18 16:20:25
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,260 bytes
コンパイル時間 969 ms
コンパイル使用メモリ 75,224 KB
実行使用メモリ 19,784 KB
最終ジャッジ日時 2025-02-02 13:30:04
合計ジャッジ時間 4,952 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

// WA

#include <iostream>
#include <vector>

constexpr int M = 1000000;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::vector<int> w(2 * M + 1);

    for (int i = 0; i < n; ++i) {
        int a, b;
        std::cin >> a >> b;
        ++w[M + a + 1];
        --w[M + b + 1];
        --w[M + a - b + 1];
    }
    // accumulate
    for (int i = 0; i < 2 * M; ++i) {
        w[i + 1] += w[i];
    }

    std::vector<long long> s(M + 1);
    s[0] = w[M];
    for (int i = 1; i <= M; ++i) {
        s[i] = w[M - i] + w[M + 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;
                s[q] += s[p * q];
            }
            for (; q >= 1; --q) {
                s[q] += s[p * q];
            }
        }
    }

    int max_f = -1, argmax = 0;
    for (int m = 1; m <= M; ++m) {
        int f_m = 1LL * -n * (M / m) - s[0] - s[m];
        if (f_m > max_f) {
            max_f = f_m;
            argmax = m;
        }
    }

    std::cout << argmax << '\n';
}
0