問題一覧 > 通常問題

No.3461 Min GCD

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 37
作問者 : くらげ / テスター : tyawanmusi dyktr_06 おのせ
ProblemId : 12837 / MMA Contest 021 (順位表) / 自分の提出
問題文最終更新日: 2026-02-27 23:37:02
MMA Contest 021の他の問題:

問題文

長さ $N$ の数列 $A, B$ があり、これに対してスコアを $\min(\gcd(A_1, B_1), \dots, \gcd(A_N, B_N))$ と定めます。
あなたは次の操作を $K$ 回まで行うことができます（ $1$ 回も行わなくてもよいです）。

  • $1 \le i \le N$ を満たす $i$ を $1$ つ選び、$B_i$ に $1$ を加算する。
適切に操作を行ったとき、スコアの最大値はいくつですか？

制約

  • $1 \le N \le 10^5$
  • $1 \le K \le 10^{10}$
  • $1 \le A_i, B_i \le 10^5$ $(1 \le i \le N)$
  • $A$, $B$ の長さは $N$
  • 入力はすべて整数

入力

$N$ $K$
$A_1$ $A_2$ $\dots$ $A_N$
$B_1$ $B_2$ $\dots$ $B_N$

出力

問題文にある操作を $K$ 回以下行った後のスコアの最大値を $1$ 行で出力してください。

サンプル

サンプル1
入力
5 12
7 10 9 7 12
25 7 16 20 22
出力
7

$B_1$ に $3$ 回、$B_2$ に $3$ 回、$B_3$ に $2$ 回、$B_4$ に $1$ 回、$B_5$ に $2$ 回の 加算を行うことで、$\gcd(A_i, B_i)$ はそれぞれ $7$、$10$、$9$、$7$、$12$ にすることが でき、この最小値は $7$ なので、$11$ 回の操作でスコア $7$ を達成できます。
$12$ 回以内の操作でスコアを $8$ 以上にすることはできないので、$7$ を出力してください。

サンプル2
入力
4 4
10 16 18 24
10 15 7 11
出力
9

サンプル3
入力
10 314
314 159 265 358 97 93 238 46 264 33
297 122 430 14 55 96 27 68 59 30
出力
5

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。