結果

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

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;

int n, K;
int a[100000];
int b[100000];
vector<int> yakus[100001];

int f(int x) {
	int sumC = 0;
	for (int i = 0; i < n; i++) {
		int minC = 1e+11;
		for (int j = (int)yakus[a[i]].size() - 1; j >= 0; j--) {
			int y = yakus[a[i]][j];
			if (y < x) break;

			int c = 0;
			if (b[i] % y != 0) c = y - b[i] % y;
			minC = min(minC, c);
			if (minC == 0) break;
		}
		sumC += minC;
	}

	return sumC;
}

signed main() {
	int i;

	cin >> n >> K;
	rep(i, n) cin >> a[i];
	rep(i, n) cin >> b[i];

	for (i = 1; i <= 100000; i++) {
		for (int j = i; j <= 100000; j += i) {
			yakus[j].push_back(i);
		}
	}

	int ok = 1, ng = 100001, mid;
	while (ng - ok >= 2) {
		mid = (ok + ng) / 2;
		if (f(mid) <= K) ok = mid;
		else ng = mid;
	}
	
	cout << ok << endl;
	return 0;
}
0