No.1059 素敵な集合
タグ : / 解いたユーザー数 229
作問者 :
Enjapma_kyopro
/ テスター :
Mister
問題文
$L$ 以上 $R$ 以下の整数をそれぞれ $1$ つずつ要素として含む、$R - L + 1$ 個の正整数からなる集合 $S$ があります。
要素が $1$ つしかない集合のことを「素敵な集合」と言います。以下の操作を繰り返すことで、 $S$ を「素敵な集合」にしたいです。
- $1$ . $S$ の相異なる $2$ つの要素、$i$ , $j$ を選ぶ。このとき、$i$ を $j$ で割ったあまりの分だけコストがかかる。
- $2$ . $i$ と $j$ のうち、好きな方を $1$ つ選んで、$S$ から削除する。
- $3$ . $S$ が「素敵な集合」であれば操作を終了し、そうでなければ手順 $1$ に戻る。
このとき、 $S$ を「素敵な集合」にするために必要なコストの合計の最小値はいくつでしょう？
入力
$L$ $R$
- 入力はすべて整数
- $1 \le L \lt R \le 2 \times 10^5$
出力
$S$ を「素敵な集合」にするために必要なコストの合計の最小値を出力してください。 最後に改行してください。
サンプル
サンプル1
入力
2 5
出力
2
まず、$3$ と $2$ を選ぶと、$3$ を $2$ で割ったあまりは $1$ なので、コスト $1$ がかかります。その後、 $3$ を削除します。
次に、$4$ と $2$ を選ぶと、$4$ を $2$ で割ったあまりは $0$ なので、コスト $0$ がかかります。その後、 $4$ を削除します。
次に、$5$ と $2$ を選ぶと、$5$ を $2$ で割ったあまりは $1$ なので、コスト $1$ がかかります。その後、 $5$ を削除します。
これで、 $S$ が「素敵な集合」になりました。かかったコストの合計は $2$ です。
サンプル2
入力
1 200000
出力
0
サンプル3
入力
5000 80000
出力
16198
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。