c++ - FF 的除数(计算给定数的除数乘积的除数数)

Question

这是一些在线比赛的问题，但现在已经结束了，所以我想知道如何真正解决它。

You are given number n and it has some (for number 4 you have 1,2,4) divisors (1 and itself included). If p is equal to product of all divisors of given number n find number of divisors of p.

我试图解决它，但我的解决方案只是优化了蛮力，所以我正在寻找具有数学背景的快速解决方案。

Answer 1

让我们看一个例子:105

105 有 8 个除数:

1, 3, 5, 7, 15, 21, 35, 105

除数乘积的除数是105^(d(105)/2)。我们可以通过配对每个除数轻松地看到这一点:

1, 3, 5, 7, 15, 21, 35, 105
a  b  c  d   d   c   b   a

=> a*a * b*b * c*c * d*d

这意味着我们将 105 乘以自身 d(105)/2 次。

现在让我们看看 105 的质因数:

3, 5 and 7

我们将在除数的乘积中得到 d(105)/2 = 4:

3*3*3*3 * 5*5*5*5 * 7*7*7*7

上述被乘数有多少种组合方式？

5 ways to set 3
5 ways to set 5
5 ways to set 7

5 * 5 * 5 = 125

105 的除数的乘积有 125 个除数。

一般公式:

f(n):
  d = product(map (\x -> x + 1) prime_counts)
  m = d / 2
  counts = map (\x -> m * x + 1) prime_counts

  return product(counts)

随机示例:

f(63):
  d = product([3, 2]) = 6
  m = 6 / 2 = 3
  counts = map (\x -> m * x + 1) [2, 1] = [7, 4]

  return product([7,4]) = 28

63 的除数的乘积，1 * 3 * 7 * 9 * 21 * 63 = 250047 有 28 个除数。