No.3054 Modulo Inequalities

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 6
作問者 :

suisen / テスター :

hamamu 👑

rin204

3 ProblemId : 11851 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2025-02-02 13:33:26

$n$ 個の正整数組 $(A_1, B_1),\ (A_2, B_2),\ \ldots,\ (A_n, B_n)$ が与えられます。

正整数 $m$ のスコア $f(m)$ を $(A_i\bmod m)\lt (B_i\bmod m)$ を満たす $i\ (1\leq i\leq n)$ の個数と定めます。ここで、$a\bmod b$ は $a$ を $b$ で割った余りを表します。

$f(m)$ が最大となる正整数 $m$ のうち、最小のものを求めてください。

入力は以下の形式で標準入力から与えられる。

$n$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_n$ $B_n$

$f(m)$ が最大となる正整数 $m$ のうち、最小のものを1行に出力して改行してください。

この入力例では $n=3$ であり、$(A_1, B_1)=(4, 9),\ (A_2, B_2)=(7, 5),\ (A_3, B_3)=(3, 6)$ です。

以下はいくつかの $m$ に対する $f(m)$ の計算例です。

$m=1$ のとき、整数を $1$ で割った余りは常に $0$ なので $f(1)=0$ です。
$m=2$ のとき、$i=1$ で $(4\bmod 2)=0\lt 1=(9\bmod 2)$ を満たしますが、他の $i$ では満たしません。従って $f(2)=1$ です。
$m=3$ のとき、$i=2$ で $(7\bmod 3)=1\lt 2=(5\bmod 3)$ を満たしますが、他の $i$ では満たしません。従って $f(3)=1$ です。
$m=4,5,6$ では $f(m)\leq 1$ です。
$m=7$ のとき、$i=2,3$ で $(A_i\bmod 7)\lt (B_i\bmod 7)$ を満たし、$i=1$ で満たしません。したがって、$f(7)=2$ です。

$f(m)\gt 2$ なる $m$ は存在しないことを証明できるので、$f(m)$ の最大値は $2$ です。また、上記より $f(m)=2$ を満たす最小の正整数 $m$ は $7$ です。従って、答えとして $7$ を出力してください。

$f(7)=7$ です。

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