#1197076 (C++23(gcc16)) No.3461 Min GCD

• 問題: No.3461 Min GCD
• ユーザー: 2251799813685248
• 提出日時: 2026-11-05 18:09:54
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 3,592 bytes
• コンパイル時間: 5,759 ms
• コンパイル使用メモリ: 370,472 KB
• 実行使用メモリ: 9,920 KB
• 最終ジャッジ日時: 2026-11-05 18:10:03
• 合計ジャッジ時間: 6,282 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge1_0

ファイルパターン	結果
sample	WA * 3
other	AC * 4 WA * 16

ソースコード

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

class Eratosthenes {
public:
    // コンストラクタにNを渡すことでN以下の整数を扱える。
    vector<bool> mark;
    vector<int> primes;   // N以下の素数リスト
    vector<int> lpf;      // iを割り切る最小の素因数(least prime factor)

    explicit Eratosthenes(int N) {
        mark.assign(N + 1, false);
        lpf.assign(N + 1, -1);

        if (N >= 1) {
            mark[1] = true;
        }

        for (int i = 2; i <= N; i++) {
            if (!mark[i]) { // iが素数のとき
                primes.push_back(i);
                lpf[i] = i; // 素数のlpfはそれ自身
                for (int j = 2 * i; j <= N; j += i) {
                    mark[j] = true;
                    if (lpf[j] == -1) { // まだjのlpfが決まっていないとき
                        lpf[j] = i;
                    }
                }
            }
        }
    }

    // 単一の整数を素因数分解
    vector<pair<int, int>> factorize(int x) const {
        if (x == 1) {
            return {{1, 0}};
        }
        vector<pair<int, int>> res;
        while (x > 1) {
            if (res.empty() || lpf[x] != res.back().first) {
                res.push_back({lpf[x], 1});
            } else {
                res.back().second += 1;
            }
            x /= lpf[x];
        }
        return res;
    }

    vector<int> enumerate_mobius(int N) const {
        vector<int> res(N + 1, 0);
        res[1] = 1;
        for (int i = 2; i <= N; i++) {
            if (i == lpf[i]) {
                res[i] = -1;
            } else {
                if ((i / lpf[i]) % lpf[i] == 0) {
                    res[i] = 0;
                } else {
                    res[i] = res[lpf[i]] * res[i / lpf[i]];
                }
            }
        }
        return res;
    }
};

vector<long long> makediv_from_primes(const vector<pair<int, int>>& p) {
    vector<long long> d = {1};
    if (p[0].first == 1) { // 1が入ってきたら例外処理
        return d;
    }

    for (const auto& v : p) { // 全方向を試す
        size_t t = d.size();
        long long temp = 1;
        for (int w = 0; w < v.second; w++) { // 実際に延長する。
            temp *= v.first;
            for (size_t i = 0; i < t; i++) {
                d.push_back(d[i] * temp);
            }
        }
    }

    sort(d.begin(), d.end());
    return d;
}

int main() {
    Eratosthenes E(100010);

    long long N, K;
    cin >> N >> K;

    vector<long long> a(N), b(N);
    for (long long i = 0; i < N; i++) cin >> a[i];
    for (long long i = 0; i < N; i++) cin >> b[i];

    vector<long long> c(100010, 0);

    for (long long i = 0; i < N; i++) {
        int n = static_cast<int>(a[i]);
        vector<long long> temp = makediv_from_primes(E.factorize(n));
        vector<long long> temp2(temp.size() + 1, LLONG_MAX);
        for (size_t idx = 0; idx < temp.size(); idx++) {
            long long m = temp[idx];
            temp2[idx] = (b[i] + m - 1) / m * m - b[i];
        }
        for (int idx = static_cast<int>(temp.size()) - 1; idx >= 0; idx--) {
            temp2[idx] = min(temp2[idx], temp2[idx + 1]);
        }
        temp.push_back(100005);
        for (size_t idx = 0; idx + 1 < temp.size(); idx++) {
            c[temp[idx]] -= temp2[idx + 1];
            c[temp[idx + 1]] += temp2[idx + 1];
        }
    }

    for (int i = 100004; i >= 0; i--) {
        c[i] += c[i + 1];
        if (c[i] <= K) {
            cout << i << endl;
            return 0;
        }
    }

    return 0;
}