結果

問題 No.3461 Min GCD
コンテスト
ユーザー tau1235
提出日時 2026-02-28 15:26:57
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 742 ms / 2,000 ms
コード長 938 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,084 ms
コンパイル使用メモリ 353,452 KB
実行使用メモリ 161,928 KB
最終ジャッジ日時 2026-02-28 15:27:30
合計ジャッジ時間 9,395 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge7
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

int main(){
	using ll=long long;
	ll n,k;
	cin>>n>>k;
	vector<int> a(n),b(n);
	for (int i=0;i<n;i++) cin>>a[i];
	for (int i=0;i<n;i++) cin>>b[i];
	vector<vector<int>> div(n);
	vector<vector<ll>> val(n);
	for (int i=0;i<n;i++){
		vector<int> divs;
		for (int j=1;j*j<=a[i];j++){
			if (a[i]%j==0){
				divs.push_back(j);
				if (j*j!=a[i]) divs.push_back(a[i]/j);
			}
		}
		sort(divs.begin(),divs.end());
		vector<ll> vec;
		for (int div:divs){
			int r=(div-b[i]%div)%div;
			vec.push_back(r);
		}
		for (int i=(int)vec.size()-1;i>=1;i--) vec[i-1]=min(vec[i-1],vec[i]);
		divs.push_back((int)2e9);
		vec.push_back((ll)2e10);
		div[i]=divs;
		val[i]=vec;
	}
	int l=0,r=1e6;
	while (r-l>1){
		int mid=(l+r)/2;
		ll nk=0;
		for (int i=0;i<n;i++){
			int j=lower_bound(div[i].begin(),div[i].end(),mid)-div[i].begin();
			nk+=val[i][j];
		}
		if (nk<=k) l=mid;
		else r=mid;
	}
	cout<<l<<endl;
}
0