用 Python 编写程序，求出除数的除数之和

pythonserver side programmingprogramming更新于 2026/1/26 14:04:17

假设我们有两个整数 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
- 如果 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))