No.2718 Best Consonance
タグ : / 解いたユーザー数 57
作問者 :
ecottea
/ テスター :
hamamu
Shirotsume
問題文
楽器 $1$ から楽器 $N$ までの $N$ 個の楽器があります．楽器 $i$ の奏でる基音の高さは $A_i$ で，その $B_i$ 倍までの倍音を含んでいます．すなわち，楽器 $i$ は高さが $A_i, 2 A_i, \ldots, B_i A_i$ の音を同時に鳴らしています．
楽器 $i$ と楽器 $j$ の調和度 $f(i, j)$ を，楽器 $i$ と楽器 $j$ が共に鳴らしている音の高さの種類数と定義します．より厳密には $$ f(i, j) := | \{ A_i, 2 A_i, \ldots, B_i A_i \} \cap \{ A_j, 2 A_j, \ldots, B_j A_j \} | $$ と定めます（$| \cdot |$ は集合の要素数を表します）．
$1 \leq i < j \leq N$ を満たす組 $(i, j)$ 全てについての調和度 $f(i, j)$ の最大値を求めてください．
制約
- $2 \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq 2 \times 10^5$
- $1 \leq B_i \leq 10^9$
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます．
$N$ $A_1 \ B_1$ $\vdots$ $A_N \ B_N$
出力
答えを出力してください． 最後に改行してください．
サンプル
サンプル1
入力
3 4 6 5 7 6 5
出力
2
それぞれの楽器が鳴らしている音の高さは
- 楽器 $1$ : $\{ 4, 8, 12, 16, 20, 24 \}$
- 楽器 $2$ : $\{ 5, 10, 15, 20, 25, 30, 35 \}$
- 楽器 $3$ : $\{ 6, 12, 18, 24, 30 \}$
です．各楽器の組の調和度は $$ \begin{aligned} f(1, 2) &= | \{ 4, 8, 12, 16, 20, 24 \} \cap \{ 5, 10, 15, 20, 25, 30, 35 \} | = | \{ 20 \} | = 1 \\ f(1, 3) &= | \{ 4, 8, 12, 16, 20, 24 \} \cap \{ 6, 12, 18, 24, 30 \} | = | \{ 12, 24 \} | = 2 \\ f(2, 3) &= | \{ 5, 10, 15, 20, 25, 30, 35 \} \cap \{ 6, 12, 18, 24, 30 \} | = | \{ 30 \} | = 1 \end{aligned} $$
となるので，これらの最大値は $2$ です．
サンプル2
入力
2 1 10 1 10
出力
10
基音の高さが等しい楽器が存在することがあります．
サンプル3
入力
2 100 1 101 1
出力
0
調和度が $0$ の組しか存在しないことがあります．
サンプル4
入力
10 2 3 9 1 4 4 7 1 5 5 3 9 6 2 1 6 8 5 1 1
出力
3
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。