問題一覧 > 通常問題

No.3461 Min GCD

レベル : / AI推定難易度 : 1600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 62
作問者 : くらげ / テスター : tyawanmusi dyktr_06 おのせ
お気に入りにしたユーザー ProblemId : 12837 / 自分の提出
問題文最終更新日: 2026-02-27 23:37:02
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
MMA Contest 021 (順位表) の他の問題:

Problem Statement

There are sequences $A, B$ of length $N$, and their score is defined as $\min(\gcd(A_1, B_1), \dots, \gcd(A_N, B_N))$.
You may perform the following operation up to $K$ times (you do not have to perform it even $1$ time).

  • Choose $1$ index $i$ satisfying $1 \le i \le N$, and add $1$ to $B_i$.
What is the maximum possible score when the operations are performed appropriately?

Constraints

  • $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)$
  • The length of $A$, $B$ is $N$
  • All input values are integers

Input

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

Output

Print on $1$ line the maximum score after performing the operation in the problem statement at most $K$ times.

Sample

Sample 1
Input
5 12
7 10 9 7 12
25 7 16 20 22
Output
7

By adding to $B_1$ $3$ times, to $B_2$ $3$ times, to $B_3$ $2$ times, to $B_4$ $1$ time, and to $B_5$ $2$ times, the values $\gcd(A_i, B_i)$ can be made $7$, $10$, $9$, $7$, $12$ respectively. Their minimum is $7$, so a score of $7$ can be achieved with $11$ operations.
It is impossible to make the score $8$ or more within $12$ operations, so print $7$.

Sample 2
Input
4 4
10 16 18 24
10 15 7 11
Output
9

Sample 3
Input
10 314
314 159 265 358 97 93 238 46 264 33
297 122 430 14 55 96 27 68 59 30
Output
5

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