Pythonの約数の約数の合計を求めるプログラム

2つの整数mとaが与えられていると仮定します。ここで、n =p ₁ ^{（a + 1）} * p ₂ ^{（a + 2）} * ... * p _m ^{（a + m）} 、ここでp _i はi番目の素数であり、i> 0です。kの値を見つける必要があります。ここで、k =nのf（x）値の合計です。ここで、f（x）値は、nの各除数の約数値の数です。

したがって、入力がm =2、a =1の場合、出力は60になります。

• つまり、n =2 ^ 2 x 3 ^ 3
• n =4 x 27
• n =108

108の約数は、1、2、3、4、6、9、12、18、27、36、54、108

各除数のf（x）値は次のとおりです。f（1）+ f（2）+ f（3）+ f（4）+ f（6）+ f（9）+ f（12）+ f（18）+ f（27）+ f（36）+ f（54）+ f（108）

=1 + 2 + 2 + 4 + 4 + 3 + 5 + 6 + 4 + 9 + 8 + 12

=60。

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

• MOD：=10 ^ 9 + 7
• 関数summ（）を定義します。これにはn
  かかります
  • （（n *（n + 1））/ 2）のフロア値を返す
• 関数division（）を定義します。これにはa、b、mod
  が必要です
  • mod bが0と同じ場合、
    • a/bのフロア値を返す
  • a：=a + mod * Division（（-a modulo b）、（mod modulo b）、b）
  • （a / b）モジュロmodのフロア値を返す
• mat：=値1を含む新しいリスト
• マットのサイズ<=m+ a、do
  • マットの最後に（マットの最後の要素* summ（len（mat）+1））modMODを挿入します
• return Division（mat [m + a]、mat [a]、MOD）

例

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

MOD = 10**9 + 7
def summ(n):
   return ((n) * (n + 1)) // 2

def division(a, b, mod):
   if a % b == 0:
      return a // b
   a += mod * division((-a) % b, mod % b, b)
   return (a // b) % mod

def solve(m, a):
   mat = [1]
   while len(mat) <= m + a:
      mat.append((mat[-1] * summ(len(mat)+1)) % MOD)
   return division(mat[m + a] , mat[a], MOD)

print(solve(2, 1))

入力

2, 1

出力

60