C++の2キーキーボード

テキストエディタに文字「A」が1つしかないとします。このレターに対して、ステップごとに2つの操作を実行できます-

• すべてコピー-メモ帳にあるすべての文字をコピーできます
• 貼り付け-前回コピーした文字を貼り付けることができます。

ここで、数nがあるとします。許可されている最小のステップ数を実行して、メモ帳で正確にn'A'を取得する必要があります。 n'A'を取得するには、最小ステップ数で結果を見つける必要があります。したがって、指定されたnが3の場合、答えは3になります。したがって、最初は「A」が1つだけです。次に、これをコピーして貼り付けると、「AA」が表示されます。これでもう一度貼り付けることができるので、1つの「A」が配置されます。したがって、「AAA」を取得します。

これを解決するには、次の手順に従います-

• ret：=0
• 2からnの範囲のkの場合
  • nmodkが0ではない場合
    • ret：=ret + kおよびn：=n / k
• return ret

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minSteps(int n) {
      int ret = 0;
      for(int k = 2; k <= n; k++){
         for(; n % k == 0; ret += k, n /= k);
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.minSteps(10));
}

入力

10

出力

7