No.3461 Min GCD
タグ : / 解いたユーザー数 62
作問者 :
くらげ
/ テスター :
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$.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。