1

我试图解决关于 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,36,100} 是完全平方。概率为 3/26。

这两个例子取自 HackerRank 上的问题描述。我解决了这个问题并通过了所有测试，但我的解决方案不是最优的。于是我阅读了HackerRank 提供的社论中提到的“Smarter Strategy” 。我理解了理论解释，但我真的被这条线弄糊涂了

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

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

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

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

在循环 2^1 之后，divisors[36] 应该是 2。然后在循环 2^2 之后，divisors[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}

但我不知道这个公式是如何从数学上推导出来的……谁能给我解释一下？太感谢了...

4

1 回答 1

0

目前尚不清楚您在谈论哪个公式，但如果您在谈论列表如何

  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 2 * 3 2并且认为你有一个列表 A = {} 最初是空的，我们会找到所有的除数。那时我想你知道质数分解是如何完成的。现在，从简单的组合学中，您可以选择三种可能的选择来2将其包含在每个除数中。假设您不想计算包含任意数量的除数，2您希望 2 0 =1 in

因此，如果您选择 2 0和任意数量，3那么您可以选择 2 0 * 3 0、2 0 * 3 1、2 0 * 3 2 因此，对于 2 0和任意数量的 3：列表包含：2 0 * 3 0 = 1、2 0 * 3 1 = 3、2 0 * 3 2 = 9

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

然后你只选择2一次，3然后你有可能的选择 2 1 * 3 0 , 2 1 * 3 1 , 2 1 * 3 2

对于 2 1和任意数量的 3：列表包含：2 1 * 3 0 = 2, 2 1 * 3 1 = 6,2 1 * 3 2 = 18

所以，A = {1, 3, 9} U {2, 6, 18} = {1, 2, 3, 6, 9, 18}并继续当2发生两次。那么你有列表中的所有除数。

这可以使用筛子轻松实现。

于 2020-05-25T17:44:54.323 回答