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

• 問題: No.3461 Min GCD
• ユーザー: detteiuu
• 提出日時: 2026-02-28 14:59:55
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 997 ms / 2,000 ms
• コード長: 4,277 bytes
• コンパイル時間: 7,270 ms
• コンパイル使用メモリ: 395,596 KB
• 実行使用メモリ: 209,348 KB
• 最終ジャッジ日時: 2026-02-28 15:00:08
• 合計ジャッジ時間: 11,801 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

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

ソースコード

#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;

#define pass (void)0
#define INF (1<<30)-1
#define INFLL (1LL<<60)-1
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define repr2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define YesNo(cond) cout << ((cond) ? "Yes\n" : "No\n")
#define YESNO(cond) cout << ((cond) ? "YES\n" : "NO\n")

using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;

template <typename T> void print(const T& value) { cout << value << "\n"; }
template <typename T> void print(const vector<T>& vec) { for (auto& v : vec) cout << v << " "; cout << "\n"; }
template <typename T> void input(vector<T>& vec) { for (auto& v : vec) cin >> v; };
template <typename T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template <typename T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }

#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
using vm = vector<mint>;

struct Eratosthenes {
    int n;
    vector<bool> isPrime;
    vector<int> minfactor;

    Eratosthenes(int n) : n(n) {
        isPrime.assign(n + 1, true);
        minfactor.assign(n + 1, -1);

        if (n >= 0) isPrime[0] = false;
        if (n >= 1) {
            isPrime[1] = false;
            minfactor[1] = 1;
        }

        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                minfactor[i] = i;
                for (long long j = 1LL * i * 2; j <= n; j += i) {
                    isPrime[j] = false;
                    if (minfactor[j] == -1) minfactor[j] = i;
                }
            }
        }
    }

    vector<pair<int,int>> factorize(long long x) const {
        vector<pair<int,int>> res;
        while (x > 1) {
            int p = minfactor[x];
            int cnt = 0;
            while (minfactor[x] == p) {
                x /= p;
                cnt++;
            }
            res.emplace_back(p, cnt);
        }
        return res;
    }

    vector<long long> divisor(long long x) const {
        vector<long long> ans = {1};
        auto pf = factorize(x);

        for (auto [p, c] : pf) {
            int L = ans.size();
            for (int i = 0; i < L; i++) {
                long long v = 1;
                for (int t = 0; t < c; t++) {
                    v *= p;
                    ans.push_back(ans[i] * v);
                }
            }
        }
        sort(all(ans));
        return ans;
    }
};

vector<vector<pll>> C;
ll N;
ll func(ll limit) {
    ll ans = 0;
    rep (i, N) {
        ll left = -1;
        ll right = sz(C[i]);
        while (left+1 < right) {
            ll mid = (left+right)/2;
            if (C[i][mid].first < limit) {
                left = mid;
            } else {
                right = mid;
            }
        }
        ans += C[i][right].second;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);

    ll K;
    cin >> N >> K;
    vl A(N);
    vl B(N);
    input(A);
    input(B);

    Eratosthenes E(100000);
    rep (i, N) {
        ll GCD = gcd(A[i], B[i]);
        vl div = E.divisor(A[i]);
        vector<pll> stack;
        stack.push_back({GCD, 0});
        for (auto d : div) {
            if (d <= GCD) continue;
            ll cnt = (((d-B[i])%d+d)%d);
            while (!stack.empty() && cnt <= stack[sz(stack)-1].second) {
                stack.pop_back();
            }
            stack.push_back({d, cnt});
        }
        C.push_back(stack);
    }
    
    rep (i, N) sort(all(C[i]));

    ll left = 1;
    ll right = INFLL;
    for (auto a : A) chmin(right, a);
    right ++;
    while (left+1 < right) {
        ll mid = (left+right)/2;
        if (func(mid) <= K) {
            left = mid;
        } else {
            right = mid;
        }
    }

    print(left);
}