結果

問題 No.3461 Min GCD
コンテスト
ユーザー wasd314
提出日時 2026-02-28 14:43:04
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 1,288 ms / 2,000 ms
コード長 2,009 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,380 ms
コンパイル使用メモリ 212,780 KB
実行使用メモリ 108,928 KB
最終ジャッジ日時 2026-02-28 14:43:13
合計ジャッジ時間 8,459 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge7
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <algorithm>
#include <iostream>
#include <map>
#include <ranges>
#include <utility>
#include <vector>
int main() {
    using namespace std;
    using lint = long long;
    int n;
    lint k;
    cin >> n >> k;
    vector<int> a(n), b(n);
    for (auto &e : a) cin >> e;
    for (auto &e : b) cin >> e;

    const int nn = 110000;
    vector isp(nn, 1);
    vector lsp(nn, -1);
    isp[0] = isp[1] = 0;
    lsp[1] = 1;
    for (int p : views::iota(2, nn)) {
        if (!isp[p]) continue;
        lsp[p] = p;
        for (int q = p * 2; q < nn; q += p) {
            isp[q] = 0;
            if (lsp[q] == -1) lsp[q] = p;
        }
    }
    auto divs = [&](int x) {
        vector<int> ans{1};
        while (x > 1) {
            int p = lsp[x];
            int e = 0;
            while (x % p == 0) {
                x /= p;
                e++;
            }
            for (int i = 0, s = ans.size(); i < s; ++i) {
                int d = ans[i] * p;
                for (int ei = 1; ei <= e; ++ei) {
                    ans.push_back(d);
                    d *= p;
                }
            }
        }
        ranges::sort(ans);
        return ans;
    };
    vector<vector<pair<int, int>>> cost(n);
    for (int i : views::iota(0, n)) {
        auto ds = divs(a[i]);
        map<int, int> dcd;
        for (int d : ds) dcd[(b[i] + d - 1) / d * d - b[i]] = d;
        for (auto [c, d] : dcd) {
            if (!cost[i].empty() && cost[i].back().first > d) {
            } else
                cost[i].emplace_back(d, c);
        }
    }
    auto check = [&](int g) {
        lint ans = 0;
        for (auto &ci : cost) {
            auto it = ranges::lower_bound(ci, g, {}, &pair<int, int>::first);
            if (it == ci.end()) return false;
            ans += it->second;
        }
        return ans <= k;
    };
    int ok = 0, ng = ranges::min(a) + 1;
    while (abs(ok - ng) > 1) {
        int mi = (ok + ng) / 2;
        (check(mi) ? ok : ng) = mi;
    }
    cout << ok << "\n";
}
0