問題一覧 > 通常問題

No.2744 Power! or +1

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 32
作問者 : Nzt3Nzt3 / テスター : ponjuiceponjuice kenken714kenken714 cho435cho435 tassei903tassei903
4 ProblemId : 10839 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-04-26 13:00:22

問題文

初め、 $X=1$ です。操作を $0$ 回以上行って $X$ を $N$ の倍数にするとき、コストの総和の最小値を求めてください。

毎回の操作では次の $3$ つの操作のうち $1$ つを選んで行います。

  1. $X$ を $X+1$ に置き換える。コストは $A$ かかる。
  2. 正整数 $k$ を選択し、 $X$ を $X^k$ で置き換える。コストは $B^k$ かかる。
  3. $X$ を $X!$ に置き換える。コストは $C$ かかる。

制約

  • $2 \le N,A,B,C \le 2 \times 10^5$
  • 入力は全て整数

入力

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

$N$ $A$ $B$ $C$

出力

答えを出力せよ。

サンプル

サンプル1
入力
12 34 56 78
出力
180

操作1を $3$ 回、操作3を $1$ 回行うとコスト $180$ で $X=24$ になります。

サンプル2
入力
199999 123 456 789
出力
2562

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