数字乘法组合

Question

给定一个正整数 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
(1, 1, 20), (1, 2, 10), (1, 4, 5), (1, 5, 4), (1, 10, 2), (1, 20, 1),
(2, 1, 10), (2, 2, 5), (2, 5, 2), (2, 10, 1), (4, 1, 5), (4, 5, 1),
(5, 1, 4), (5, 2, 2), (5, 4, 1), (10, 1, 2), (10, 2, 1), (20, 1, 1) -> 18

我试图计算数字的所有除数并将结果乘以 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) #output [(1, 24), (2, 12), (3, 8), (4, 6)]
print(len(new)*2) #output 8

Answer 1

如果你需要看路，而不是只数路

这是一个基于您的起点的程序

def list_of_factor_lists(n,length):
  if length==1:
    return [[n]]

  elif length==2:
    return  [[d, n // d] for d in range(1, n + 1) if n % d == 0]

  else:
    first_divisors = [pair[0] for pair in div_pairs(n)]
    result = []
    for first_divisor in first_divisors:
      remainder = n//first_divisor
      list_of_other_factor_lists = list_of_factor_lists(remainder,length-1)
      result.extend([first_divisor, *other_divisors] for other_divisors in list_of_other_factor_lists)
    return result
  

results = list_of_factor_lists(100,3)
for result in results:
  print(result)

注意平方数

对于他们来说，计数不仅仅是从循环到平方根的值加倍 - 多算 1。为简单起见，我已经上升到 n，但你也可以专门为平方捏造它。

Answer 2

一种选择是递归计算：

def count_ways(n, k):
    if n == 0 or k == 0:
        return 0
    elif k == 1:
        return 1
    else:
        count = 0
        for i in range(1, n+1):
            if n % i == 0:
                count += count_ways(n//i, k-1)
        return count

另一种选择：

from itertools import combinations_with_replacement

def count_ways(n, k):
    combs = combinations_with_replacement(range(1, n+1), k)
    count = 0
    for comb in combs:
        if prod(comb) == n:
            count += 1
    return count

函数

combinations_with_replacement

生成从1到n范围内的k元素的所有可能组合，其中每个元素可以重复任意次数。

Answer 3

递归可能是最简单的方法：

def prodWays(N,k):
    if k < 2: return k
    return sum(prodWays(N//f,k-1)+prodWays(f,(k-1)*(f*f<N))
               for f in range(1,int(N**0.5)+1) if N%f==0)

输出：

print(prodWays(24,2)) # 8
print(prodWays(20,3)) # 18

注

(k-1)*(f*f<N)

用于避免N为平方数时重复计算根