結果

問題 No.3461 Min GCD
コンテスト
ユーザー cho435
提出日時 2026-02-28 15:09:05
言語 C++23(gnu拡張)
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=gnu++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 680 ms / 2,000 ms
コード長 1,908 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,692 ms
コンパイル使用メモリ 357,252 KB
実行使用メモリ 147,184 KB
最終ジャッジ日時 2026-02-28 15:09:19
合計ジャッジ時間 11,191 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge7
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
// #include <atcoder/all>

namespace cho {
std::vector<int> prime_table(int n) {
	std::vector<int> p(n + 1, -1);
	for (int i = 2; i * i <= n; i++) {
		if (p[i] != -1) continue;
		for (int j = i * i; j <= n; j += i) p[j] = i;
	}
	return p;
}
std::map<int, int> table_factor(int n) {
	const static std::vector<int> table = prime_table(1e7);
	assert(n <= 1e7);
	std::map<int, int> res;
	while (n > 1) {
		if (table[n] == -1) {
			res[n]++;
			break;
		}
		res[table[n]]++;
		n /= table[n];
	}
	return res;
}
std::vector<int> all_factors(int n) {
	assert(n <= 1e7);
	std::vector<int> res = {1};
	int sz = 1;
	for (auto [x, ad] : table_factor(n)) {
		for (int i = 0; i < ad * sz; i++) {
			res.push_back(res[i] * x);
		}
		sz *= ad + 1;
	}
	return res;
}
}  // namespace cho

using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define all(x) begin(x), end(x)
template <class T> bool chmin(T& x, T y) {
	return x > y ? (x = y, true) : false;
}
template <class T> bool chmax(T& x, T y) {
	return x < y ? (x = y, true) : false;
}

void solve() {
	ll n, k;
	cin >> n >> k;
	vector<int> a(n), b(n);
	rep(i, 0, n) cin >> a[i];
	rep(i, 0, n) cin >> b[i];
	vector<vector<pair<int, int>>> da(n);
	int up = 1e9;
	int dw = 1;
	rep(i, 0, n) {
		auto v = cho::all_factors(a[i]);
		sort(all(v));
		for (int x : v) {
			int ct = (x - b[i] % x) % x;
			while (!da[i].empty() && da[i].back().second >= ct)
				da[i].pop_back();
			da[i].push_back({x, ct});
		}
		chmin(up, a[i]);
	}
	up++;
	while (up - dw > 1) {
		int md = (up + dw) / 2;
		ll tk = 0;
		rep(i, 0, n) {
			auto [x, ct] = *lower_bound(all(da[i]), pair(md, -1));
			tk += ct;
		}
		if (tk <= k) dw = md;
		else up = md;
	}
	cout << dw << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(15);
	int t = 1;
	// cin >> t;
	while (t--) solve();
}
0