結果

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

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main () {
	int N; ll K;
	cin >> N >> K;
	std::vector<ll> A(N), B(N);
	for (auto& a : A) {
		cin >> a;
	}
	for (auto& b : B) {
		cin >> b;
	}
	int L = *max_element(A.begin(), A.end());
	vector<ll> C(L + 1, 0ll);
	map<int, int> X;
	for (int i = 0; i < N; i ++) {
		X.clear();
		int a = A[i], b = B[i];
		for (int x = 1; x * x <= a; x ++) {
			if (a % x == 0) {
				int d = b % x;
				d = (d ? x - d : d);
				X[d] = max(X[d], x);
				int y = a / x;
				d = b % y;
				d = (d ? y - d : d);
				X[d] = max(X[d], y);
			}
		}
		int c1 = 1, c2 = 0;
		for (auto& [k, v] : X) {
			if (c1 < v) {
				C[c1+1] += (k - c2);
				c2 = k;
				c1 = v;
			}
		}
		C[a+1] = K;
	}
	for (int i = 0; i <= L; i ++) {
		K -= C[i];
		if (K < 0) {
			cout << i-1 << endl;
			return 0;
		}
	}
	cout << L << endl;
}
0