Pythonで素敵な除数の数を最大化するプログラム

数pfが素因数の数を表すと仮定します。次の条件を満たす正の数nを作成する必要があります-

• nの素因数の数（明確である場合とそうでない場合があります）は、最大でpfです。

• nの素敵な除数の数が最大化されます。私たちが知っているように、nの約数は、nのすべての素因数で割り切れるときに便利です。

nの約数の除数を見つける必要があります。答えが大きすぎる場合は、10 ^ 9+7を法とする結果を返します。

したがって、入力がpf =5の場合、出力は6になります。これは、n =200の場合、素因数[2,2,2,5,5]があり、その約数が[10,20,40,50,100,200]であるためです。 ]だから6除数。

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

• pfが1と同じ場合、

  • 1を返す

• m：=10 ^ 9 + 7

• q：=pf / 3の商、r：=pf mod 3

• rが0と同じ場合、

  • 3 ^ qmodmを返す

• それ以外の場合、rが1と同じ場合、

  • return（3 ^（q-1）mod m）* 4 mod m

• それ以外の場合

  • return（3 ^ q mod m）* 2 mod m

例

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

def solve(pf):
   if pf == 1:
      return 1
   m = 10** 9 + 7
   q, r = divmod(pf, 3)
   if r == 0:
      return pow(3, q, m)
   elif r == 1:
      return pow(3, q-1, m) * 4 % m
   else:
      return pow(3, q, m) * 2 % m

pf = 5
print(solve(pf))

入力

5

出力

6