問題一覧 > 通常問題

No.2718 Best Consonance

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 58
作問者 : ecottea / テスター : hamamu Shirotsume
3 ProblemId : 10603 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-12 00:11:20

問題文

楽器 11 から楽器 NN までの NN 個の楽器があります．楽器 ii の奏でる基音の高さは AiA_i で，その BiB_i 倍までの倍音を含んでいます．すなわち，楽器 ii は高さが Ai,2Ai,…,BiAiA_i, 2 A_i, \ldots, B_i A_i の音を同時に鳴らしています．

楽器 ii と楽器 jj の調和度 f(i,j)f(i, j) を，楽器 ii と楽器 jj が共に鳴らしている音の高さの種類数と定義します．より厳密には f(i,j):=∣{Ai,2Ai,…,BiAi}∩{Aj,2Aj,…,BjAj}∣ 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≤i<j≤N1 \leq i < j \leq N を満たす組 (i,j)(i, j) 全てについての調和度 f(i,j)f(i, j) の最大値を求めてください．

制約

  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • 1≤Ai≤2×1051 \leq A_i \leq 2 \times 10^5
  • 1≤Bi≤1091 \leq B_i \leq 10^9
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられます．

NN
A1 B1A_1 \ B_1
⋮\vdots
AN BNA_N \ B_N

出力

答えを出力してください． 最後に改行してください．

サンプル

サンプル1
入力
3
4 6
5 7
6 5
出力
2

それぞれの楽器が鳴らしている音の高さは

  • 楽器 11 : {4,8,12,16,20,24}\{ 4, 8, 12, 16, 20, 24 \}
  • 楽器 22 : {5,10,15,20,25,30,35}\{ 5, 10, 15, 20, 25, 30, 35 \}
  • 楽器 33 : {6,12,18,24,30}\{ 6, 12, 18, 24, 30 \}

です．各楽器の組の調和度は f(1,2)=∣{4,8,12,16,20,24}∩{5,10,15,20,25,30,35}∣=∣{20}∣=1f(1,3)=∣{4,8,12,16,20,24}∩{6,12,18,24,30}∣=∣{12,24}∣=2f(2,3)=∣{5,10,15,20,25,30,35}∩{6,12,18,24,30}∣=∣{30}∣=1 \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}

となるので，これらの最大値は 22 です．

サンプル2
入力
2
1 10
1 10
出力
10

基音の高さが等しい楽器が存在することがあります．

サンプル3
入力
2
100 1
101 1
出力
0

調和度が 00 の組しか存在しないことがあります．

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