問題一覧 > 通常問題

No.1737 One to N

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 150
作問者 : ShirotsumeShirotsume / テスター : とりゐとりゐ nok0nok0
4 ProblemId : 6461 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-11-06 00:09:32

問題文

あなたは整数 $X$ を持っています。初め、 $X = 1$ です。

あなたは整数 $X$ に対して次の操作を $0$ 回以上好きな回数行うことができます。

    操作: $2$ 以上の整数を $1$ つ選び、選んだ整数を $K$ とする。$K$ 円を支払い、 $X$ を $KX$ に置き換える。

正の整数 $N$ が与えられるので、$X = N$ にするために必要な最小金額を求めてください。

制約

  • $ 1 \leq N \leq 3 \times 10^5$
  • $N$ は整数

入力

入力は以下の形式で標準入力から与えられる。
$N$

出力

必要な最低金額を出力せよ。 最後に改行すること。

サンプル

サンプル1
入力
12
出力
7

初め、 $X = 1$ です。$1$ 回目の操作で $K = 3$ とすると、あなたは $3$ 円を支払い、 $X$ が $3 \times 1 = 3$ に置き換わります。

$2$ 回目の操作で $K = 4$ とすると、あなたは $4$ 円を支払い、 $X$ が $4 \times 3 = 12$ に置き換わります。

以上の手順で、合計 $7$ 円支払うことで $X = N$ にできます。 $7$ 円未満で $X = N$ とできる手順は存在しないので、 $7$ を出力してください。

サンプル2
入力
123456
出力
658

サンプル3
入力
1
出力
0

もともと $X = 1$ であるため、お金を支払う必要はありません。

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