問題一覧 > 通常問題

No.2718 Best Consonance

レベル : / AI推定難易度 : 2325 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 58
作問者 : ecottea / テスター : 👑 hamamu Shirotsume
お気に入りにしたユーザー ProblemId : 10603 / 自分の提出
問題文最終更新日: 2024-03-12 00:11:20
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 426 (順位表) の他の問題:

Problem Statement

There are $N$ instruments, numbered from instrument $1$ to instrument $N$. The fundamental tone played by instrument $i$ has pitch $A_i$, and the instrument includes overtones up to $B_i$ times that pitch. That is, instrument $i$ simultaneously sounds tones of pitches $A_i, 2 A_i, \ldots, B_i A_i$.

The degree of harmony $f(i, j)$ of instruments $i$ and $j$ is defined as the number of distinct pitches sounded by both instrument $i$ and instrument $j$. More precisely, it is defined as $$ f(i, j) := | \{ A_i, 2 A_i, \ldots, B_i A_i \} \cap \{ A_j, 2 A_j, \ldots, B_j A_j \} | $$ (where $| \cdot |$ denotes the number of elements in a set).

Find the maximum value of the degree of harmony $f(i, j)$ over all pairs $(i, j)$ satisfying $1 \leq i < j \leq N$.

Constraints

  • $2 \leq N \leq 2 \times 10^5$
  • $1 \leq A_i \leq 2 \times 10^5$
  • $1 \leq B_i \leq 10^9$
  • All input values are integers.

Input

The input is given from standard input in the following format.

$N$
$A_1 \ B_1$
$\vdots$
$A_N \ B_N$

Output

Output the answer. Print a newline at the end.

Sample

Sample 1
Input
3
4 6
5 7
6 5
Output
2

The pitches sounded by each instrument are as follows.

  • Instrument $1$ : $\{ 4, 8, 12, 16, 20, 24 \}$
  • Instrument $2$ : $\{ 5, 10, 15, 20, 25, 30, 35 \}$
  • Instrument $3$ : $\{ 6, 12, 18, 24, 30 \}$

The degree of harmony of each pair of instruments is $$ \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} $$

so the maximum of these is $2$.

Sample 2
Input
2
1 10
1 10
Output
10

There may be instruments with the same fundamental pitch.

Sample 3
Input
2
100 1
101 1
Output
0

It is possible that only pairs with a degree of harmony of $0$ exist.

Sample 4
Input
10
2 3
9 1
4 4
7 1
5 5
3 9
6 2
1 6
8 5
1 1
Output
3

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