求k个有序正整数相乘等于n的组合数的技术问询

给定正整数n，返回满足k个正整数相乘结果为n的有序组合数量（顺序不同视为不同组合）。
示例：

• n=24，k=2时，组合有(1,24),(2,12),(3,8),(4,6),(6,4),(8,3),(12,2),(24,1)，共8种；
• n=100，k=1时，仅100这1种；
• n=20，k=3时，共有18种组合。

你尝试通过统计n的因数对并乘以2的方法计算，但该方法仅适用于k=2的场景，无法处理k>2的情况，附上你的尝试代码：

from itertools import *

divs = lambda n: [(d, n // d) for d in range(1, int(n ** 0.5) + 1) if n % d == 0]
new = list(divs(24))
print(new) # 输出 [(1, 24), (2, 12), (3, 8), (4, 6)]
print(len(new)*2) # 输出 8

解决方案：质因数分解+组合数学 #

核心思路 #

1. 质因数分解：先将n分解为质因数的幂次形式：(n = p_1^{a_1} \times p_2^{a_2} \times ... \times p_m^{a_m})
2. 指数分配：问题等价于把每个质因数的指数(a_i)分配到k个位置上（每个位置的指数可以为0，对应该位置的数不含此质因数）。每个质因数的分配是独立事件，总组合数为所有质因数分配方式的乘积。
3. 组合数计算：对于单个指数(a_i)，分配到k个位置的方式数为可重复组合数(C(a_i + k - 1, k - 1))（即把(a_i)个相同的球放到k个不同盒子，允许空盒的方案数）。

举个例子：n=20=2²×5¹，k=3

• 质因数2的指数是2，分配方式为(C(2+3-1,3-1)=C(4,2)=6)
• 质因数5的指数是1，分配方式为(C(1+3-1,3-1)=C(3,2)=3)
• 总组合数=6×3=18，与示例一致。

代码实现 #

import math

def prime_factorize(n):
    """对n进行质因数分解，返回{质因数: 指数}的字典"""
    factors = {}
    # 处理2的情况
    while n % 2 == 0:
        factors[2] = factors.get(2, 0) + 1
        n = n // 2
    # 处理奇数
    i = 3
    while i * i <= n:
        while n % i == 0:
            factors[i] = factors.get(i, 0) + 1
            n = n // i
        i += 2
    # 剩余的大于2的质因数
    if n > 2:
        factors[n] = 1
    return factors

def count_ordered_combinations(n, k):
    """计算k个正整数乘积为n的有序组合数"""
    if k == 1:
        return 1
    factors = prime_factorize(n)
    total = 1
    for exp in factors.values():
        # 计算组合数C(exp + k -1, k-1)
        total *= math.comb(exp + k - 1, k - 1)
    return total

# 测试示例
print(count_ordered_combinations(24, 2))  # 输出: 8
print(count_ordered_combinations(100, 1)) # 输出: 1
print(count_ordered_combinations(20, 3))  # 输出: 18

补充说明 #

• 若你的Python版本低于3.10（math.comb是3.10新增函数），可以自行实现组合数计算：

  def comb(n, r):
      if r < 0 or r > n:
          return 0
      if r == 0 or r == n:
          return 1
      r = min(r, n - r)
      numerator = 1
      for i in range(n, n - r, -1):
          numerator *= i
      denominator = 1
      for i in range(1, r + 1):
          denominator *= i
      return numerator // denominator
  

  然后将代码中的math.comb替换为这个自定义函数即可。

内容的提问来源于stack exchange，提问作者артем костриков