No.3054 Modulo Inequalities
Problem Statement
You are given $n$ pairs of positive integers $(A_1, B_1),\ (A_2, B_2),\ \ldots,\ (A_n, B_n)$.
Define the score $f(m)$ of a positive integer $m$ as the number of $i\ (1\leq i\leq n)$ satisfying $(A_i\bmod m)\lt (B_i\bmod m)$. Here, $a\bmod b$ denotes the remainder when $a$ is divided by $b$.
Find the smallest positive integer $m$ among those that maximize $f(m)$.
Input
The input is given from standard input in the following format.
$n$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_n$ $B_n$
- All inputs are integers.
- $1\leq n\leq 5\times 10^5$
- $1\leq A_i \leq 10 ^ 6\ (1\leq i\leq n)$
- $1\leq B_i \leq 10 ^ 6\ (1\leq i\leq n)$
Output
Output on one line the smallest positive integer $m$ among those that maximize $f(m)$, followed by a newline.
Sample
Sample 1
Input
3 4 9 7 5 3 6
Output
7
In this sample, $n=3$ and $(A_1, B_1)=(4, 9),\ (A_2, B_2)=(7, 5),\ (A_3, B_3)=(3, 6)$.
Below are examples of computing $f(m)$ for some values of $m$.
- When $m=1$, the remainder of any integer divided by $1$ is always $0$, so $f(1)=0$.
- When $m=2$, the condition $(4\bmod 2)=0\lt 1=(9\bmod 2)$ holds for $i=1$, but it does not hold for the other $i$. Therefore, $f(2)=1$.
- When $m=3$, the condition $(7\bmod 3)=1\lt 2=(5\bmod 3)$ holds for $i=2$, but it does not hold for the other $i$. Therefore, $f(3)=1$.
- For $m=4,5,6$, we have $f(m)\leq 1$.
- When $m=7$, the condition $(A_i\bmod 7)\lt (B_i\bmod 7)$ holds for $i=2,3$ and does not hold for $i=1$. Therefore, $f(7)=2$.
It can be proved that no $m$ with $f(m)\gt 2$ exists, so the maximum value of $f(m)$ is $2$. Also, from the above, the smallest positive integer $m$ satisfying $f(m)=2$ is $7$. Therefore, output $7$ as the answer.
Sample 2
Input
10 1 3 3 6 4 1 7 8 8 4 9 5 10 5 10 8 5 6 3 3
Output
7
$f(7)=7$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
hamamu