No.2718 Best Consonance
タグ : / 解いたユーザー数 58
作問者 :
hamamu
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もしくは右上の雲マークをクリックしてアカウントを作成してください。