求给定数N的偶完全平方真因子的个数

Question

我试图解决一个关于HackerRank（问题链接：https://www.hackerrank.com/challenges/mehta-and-his-laziness/problem）的问题，该问题涉及计算给定数字N的偶完美平方真除数的个数。该问题要求程序计算给定数字N的除数在所有N的真除数中是偶完美平方的概率

例如，给定N=36，适当因子集是{1,2,3,4,6,9,12,18}，只有4是偶完美平方。概率为1/8

另一个例子是N=900，总共有26个真因子，其中3个{4,36100}甚至是完全平方。概率为3/26

这两个示例取自HackerRank上的问题描述。我解决了这个问题并通过了所有测试，但我的解决方案不是最优的。因此，我阅读了HackerRank提供的社论中提到的“更聪明的策略”。我理解理论上的解释，但我被这句话弄糊涂了

divisors[j] += divisors[j] / e

我不知道复制并粘贴HackerRank（https://www.hackerrank.com/challenges/mehta-and-his-laziness/editorial）社论中的解释和完整代码是否合适，因为它要求用户首先登录（可以使用Gmail、Facebook、GitHub和LinkedIn帐户）并解锁（无需付费，这是免费的），所以我只是粘贴了我感到非常困惑的一行。我希望有人也能访问这篇社论并回答我的以下问题

我理解其他解决方案的解释和代码，但我不明白为什么要用这种方法来更新除数列表。除数[j]是循环最后一个周期的值，如何计算当前素数和特定指数产生的除数？我认为它是/e而不是/（e+1）是因为列表中所有1的初始化（已经计算出1是每个数字的除数）。另外，我认为这种更新方法是为了避免重复计算，但我真的不明白这个公式是如何推导出来的

例如，36=2^2*3^2

在循环2^1之后，除数[36]应该是2。在循环2^2之后，除数[36]应该是3（2/2+2）。在循环3^1之后，除数[36]应该是6（3/1+3）。在3^2之后，除数[36]应该是9（6/2+6）

我的猜测是，在每个循环之后，除数都在添加由当前值引起的除数的可能性，例如，在36的情况下：

val：除数列表
2^1:{1,2}
2^2:{1,2,4}
3^1:{1,2,4,3,6,12}
3^2:{1,2,4,3,6,12,9,18,36}

但我不知道这个公式是如何从数学上推导出来的。。。谁能给我解释一下吗？非常感谢你

Answer 1

现在还不清楚你说的是哪一个公式，但如果你说的是列表是如何显示的

  val : divisors list
  2^1 : {1,2}
  2^2 : {1,2,4}
  3^1 : {1,2,4,3,6,12}
  3^2 : {1,2,4,3,6,12,9,18,36}

这就是答案 你的数字是36=2²*3²并且认为你有一个列表a={}，它最初是空的，我们会找到所有的除数。在这一点上，我想你知道素数分解是如何完成的。 现在，从简单的组合数学中，你有三种可能的选择2将它包含在每个除数中。 假设您不想计算包含任意数目的2的除数，这意味着您希望2⁰=1

因此，如果您选择2⁰和任意数量的3，那么您可以选择2⁰*3⁰，2⁰*3¹，2⁰*3² 因此，对于2⁰和任意数量的3:list包含：2⁰*3⁰=1，2⁰*3¹=3，2⁰*3²=9

所以，A = {1, 3, 9}

然后你选择一次2和任意数量的3，然后你有可能选择2¹*3⁰，2¹*3¹，2¹*3²

对于2¹和任意数量的3:list包含：2¹*3⁰=2，2¹*3¹=6,2⁼¹⁸

所以，A = {1, 3, 9} U {2, 6, 18} = {1, 2, 3, 6, 9, 18}并在2出现两次时继续。然后你得到了列表中的所有除数

这可以使用sieve轻松实现