問題一覧 > 通常問題

No.1059 素敵な集合

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 164
作問者 : Enjapma_kyoproEnjapma_kyopro / テスター : MisterMister
40 ProblemId : 4272 / 出題時の順位表
問題文最終更新日: 2020-05-29 23:10:13

問題文

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