Python程式：求所有因子的因子的個數之和

假設我們有兩個整數m和a。現在n = p1(a + 1) *p2(a + 2) *...*pm(a + m)，其中pi是第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作為引數。
    • 如果a mod b等於0，則
      • 返回a / b的向下取整值。
    • a := a + mod * division((-a modulo b), (mod modulo b), b)
    • 返回(a / b) modulo mod的向下取整值。
  • mat := 一個包含值1的新列表。
  • 當mat的長度 <= m + a時，執行以下操作：
    • 在mat的末尾插入 (mat的最後一個元素 * summ(len(mat)+1)) mod MOD。
  • 返回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

更新於：2021年10月20日

瀏覽量：198

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告