問題一覧 > 通常問題

No.3054 Modulo Inequalities

レベル : / AI推定難易度 : 2400 / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 11
作問者 : suisen / テスター : 👑 hamamu 👑 rin204
お気に入りにしたユーザー ProblemId : 11851 / 自分の提出
問題文最終更新日: 2025-02-02 13:33:26
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
yukicoder contest 459 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。