No.1059 Nice Set
タグ : / 解いたユーザー数 239
作問者 :
Enjapma_kyopro
/ テスター :
Mister
Problem Statement
There is a set $S$ of $R - L + 1$ positive integers that contains $1$ copy of each integer between $L$ and $R$, inclusive, as its elements.
A set with only $1$ element is called a "nice set". You want to make $S$ a "nice set" by repeating the following operation.
- $1$ . Choose $2$ distinct elements of $S$, $i$ , $j$ . This incurs a cost equal to the remainder of $i$ divided by $j$.
- $2$ . Choose whichever $1$ of $i$ and $j$ you like and remove it from $S$.
- $3$ . If $S$ is a "nice set", end the operation; otherwise, return to step $1$.
What is the minimum total cost required to make $S$ a "nice set"?
Input
$L$ $R$
- All inputs are integers.
- $1 \le L \lt R \le 2 \times 10^5$
Output
Output the minimum total cost required to make $S$ a "nice set". Print a newline at the end.
Sample
Sample 1
Input
2 5
Output
2
First, choose $3$ and $2$. The remainder of $3$ divided by $2$ is $1$, so a cost of $1$ is incurred. Then, remove $3$.
Next, choose $4$ and $2$. The remainder of $4$ divided by $2$ is $0$, so a cost of $0$ is incurred. Then, remove $4$.
Next, choose $5$ and $2$. The remainder of $5$ divided by $2$ is $1$, so a cost of $1$ is incurred. Then, remove $5$.
Now $S$ has become a "nice set". The total cost incurred is $2$.
Sample 2
Input
1 200000
Output
0
Sample 3
Input
5000 80000
Output
16198
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。