#1151217 (C++23) No.3461 Min GCD

• 問題: No.3461 Min GCD
• ユーザー: Tatsu_mr
• 提出日時: 2026-03-04 15:08:56
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 359 ms / 2,000 ms
• コード長: 2,938 bytes
• コンパイル時間: 3,773 ms
• コンパイル使用メモリ: 348,824 KB
• 実行使用メモリ: 109,300 KB
• 最終ジャッジ日時: 2026-03-04 15:09:06
• 合計ジャッジ時間: 7,369 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
sample	AC * 3
other	AC * 21

ソースコード

#include <bits/stdc++.h>
using namespace std;

#define For(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, n) For(i, 0, n)
#define rFor(i, a, b) for(int i = (a); i >= (b); i--)
#define ALL(v) (v).begin(), (v).end()
#define rALL(v) (v).rbegin(), (v).rend()
#define SZ(v) ((int)(v).size())

using lint = long long;
using ld = long double;

const int INF = 1001001001;
const lint LINF = 4004004003094073385LL;
// 真上から反時計回り
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, -1, 0, 1};
const int di8[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dj8[] = {0, -1, -1, -1, 0, 1, 1, 1};

struct SetupIo {
    SetupIo() {
        ios::sync_with_stdio(false); cin.tie(nullptr);
        cout << fixed << setprecision(15);
        cerr << fixed << setprecision(15);
    }
} setupio;

namespace tatsumr {

template <class T>
bool chmin(T &a, const T &b) {
    return a > b ? a = b, 1 : 0;
}
template <class T>
bool chmax(T &a, const T &b) {
    return a < b ? a = b, 1 : 0; 
}
template <class T>
T div_floor(T a, T b) {
    assert(b != 0);
    if (b < 0) {
        a = -a;
        b = -b;
    }
    return (a >= 0 ? a / b : (a + 1) / b - 1);
}
template <class T>
T div_ceil(T a, T b) {
    assert(b != 0);
    if (b < 0) {
        a = -a;
        b = -b;
    }
    return (a > 0 ? (a - 1) / b + 1 : a / b);
}
template <class T>
T mypow(T a, T b) {
    T res = 1;
    while (b) {
        if (b & 1) { res *= a; }
        a *= a; b >>= 1;
    }
    return res;
}
template <class T>
T modpow(T a, T b, T mod) {
    T res = 1;
    while (b) {
        if (b & 1) { res = (res * a) % mod; }
        a = (a * a) % mod; b >>= 1;
    }
    return res;
}

} // namespace tatsumr

using namespace tatsumr;

int main() {
    lint N, K;
    cin >> N >> K;
    vector<lint> A(N), B(N);
    rep(i, N) {
        cin >> A[i];
    }
    rep(i, N) {
        cin >> B[i];
    }
    vector<vector<lint>> ds;
    rep(i, N) {
        vector<lint> d;
        for (lint x = 1; x * x <= A[i]; x++) {
            if (A[i] % x == 0) {
                d.emplace_back(x);
                d.emplace_back(A[i] / x);
            }
        }
        sort(ALL(d));
        d.erase(unique(ALL(d)), d.end());
        ds.emplace_back(d);
    }
    // スコアを x 以上にできるか？
    auto judge = [&](lint x) -> bool {
        lint tmp = 0;
        rep(i, N) {
            lint cnt = LINF;
            rFor(j, SZ(ds[i]) - 1, 0) {
                lint g = ds[i][j];
                if (g < x) break;
                // gcd(A[i], B[i]) = g にする
                lint q = div_ceil<lint>(B[i], g);
                lint goal = g * q;
                chmin(cnt, goal - B[i]);
            }
            if (cnt == LINF) return false;
            tmp += cnt;
        }
        return tmp <= K;
    };
    lint ac = 1, wa = 100010;
    while (wa - ac > 1) {
        lint wj = (ac + wa) / 2;
        (judge(wj) ? ac : wa) = wj;
    }
    cout << ac << "\n";
}