问题标签 [perfect-square]

我想制作一个程序来获取数字输入并找到最接近的完美正方形来确定正方形长度。因此，最接近的完美平方必须小于输入。比如输入8，正方形的最大边长是2。问题是程序会要求我输入一个数字，但之后没有输出任何东西。它还说我有一个重复的局部变量 a1。

所以我试图找出一组数字中的完美正方形。我声明了必要的变量，添加了一个 for 循环，添加了sqroot = Math.sqrt(num)一个打印方法来列出数字。我想不通的是如何让程序在数字范围内挑选出完美的正方形，并找到它们的平均值？

这是我正在为一堂课做的一项作业，我已经坚持了一段时间了。如果这是一个愚蠢的问题，我对 Java 也很陌生，很抱歉。代码如下：

这只是整个作业中的一部分代码，所以如果您需要更多代码，那么我非常愿意提供它。谢谢！

你有两个列表，你必须找出构成完美正方形的对。

例如在：

有两对(2,8)和(8,18)。

有没有比蛮力更有效的方法？这是我的代码，其时间复杂度为 O(n*m)（其中 n 是 a 的长度，m 是 b 的长度）。

在这里使用 C# 之前已经问过这个问题，但我不明白“我们需要为每个数字存储的只是它的哪个素数具有奇数”的意思，所以我无法在我的 Python 代码。

有人可以向我解释我们如何在 Python 中实现一个有效的解决方案吗？

完美平方数的例子是1,4,9,16,25....

我们如何计算非常大的数字（例如 10 pow 20）的所有完美平方数。对于 10 pow 20，有 10 个 pow 10 完美平方数。

到目前为止我所做的......

Bruteforce：计算 x**2 在 1 到 10 pow 10 的范围内。因为我的系统只接受 10 pow 6。这不起作用。

两个指针的方法：我已经取了上限和下限....

上限为 10 pow 20

下界为 1

现在，我拿了两个指针，一个在开始，另一个在结束。然后下界的下一个完美正方形将是

下限 + (sqrt(下限) *2+1)

示例：对于 4 下一个完美正方形是

4 + (sqrt(4)*2+1)= 9

以同样的方式上限将减少

上限 - (sqrt(上限) *2-1)

示例：对于 25，之前的完美正方形是

25 - (sqrt(25)*2-1) =16

上述两种方法都不能很好地工作，因为上限是非常非常大的数字 10 pow 20。

我们怎样才能在更短的时间内有效地计算出所有完美的平方，直到 10 pow 20 ？

考虑伪代码：

我必须修改这个伪代码，使其中没有循环，所以我必须摆脱顶部的那个 while 循环。我浏览了一些示例，即数字{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100}和代码导致显示N数字，并且显示数字{2, 3, 5, 6, 7, 8}和它们各自的平方根（分别）。{1, 4, 9, 100}D{1, 2, 3, 10}

所以我得出结论，代码D只有在n是一个完美平方时才输出，然后它显示它的平方根。对于不是完全平方的数字，它输出N.

这意味着我必须更改上面的伪代码，以便它检查数字n是否是完美的正方形。但是我怎么能在不使用任何循环的情况下做到这一点呢？特别是因为这是伪代码，所以我没有像sqrt(n). 我从一个通常有简单问题的来源得到这个练习，所以它一定是一些我看不到的简单的东西，没有什么复杂的。但是我看不到任何使用给定变量的方法，或者创建新变量来检查给定数字n是否是没有任何循环的完美正方形。

我正在解决一个问题，我必须确定给定的数字是否是斐波那契数。

它涉及一个步骤，我们必须检查 5*n*n-4 或 5*n*n+4（n 是给定的数字并且总是大于 0）是否是完美的正方形。如果这些术语中的任何一个或两者都是完美的正方形，那么它就是斐波那契数，否则不是。

我使用下面的语句来检查一个完美的正方形。

但是这种方法对 4 个测试用例显示了错误的答案。

而当我使用这个（下面）方法时，它通过了所有测试用例。

上述两种寻找完美正方形的方法有什么区别？

它是否也会影响程序的时间复杂度？

如何解释列表理解表达式不起作用（python 3.8.2 32bit env）：

对比：

第一个给出 None 值的数组？理解表达式无权访问 psqares 堆栈？

我试图解决关于 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” 。我理解了理论解释，但我真的被这条线弄糊涂了

我不知道是否适合从 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}

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

试图通过递归和记忆来解决这个问题，但是对于输入 7168，我得到了错误的答案。

我这样打电话：

所有的测试用例都通过了（甚至是复杂的用例），但是这个失败了。我怀疑我的记忆有问题，但无法确定到底是什么。任何帮助将不胜感激。

问题陈述：

使用以下有关正方形的知识（如下所示），我们可以实现以下解决方案。

自然数是...

1. ...当且仅当每个素因数在数字的素因数分解中出现偶数次方时，方格。
2. ...两个平方的和当且仅当每个 3 模 4 的素数因数在数字的素数因式分解中出现偶数幂。
3. ...三个平方和当且仅当它不是具有整数 a 和 b 的 4a(8b+7) 形式。
4. ...四个平方的总和。时期。没有条件。你永远不需要超过四个。

问题：

有人可以帮助我了解我们在执行 for 循环时到底要达到什么目标吗？我在这里有点迷路了。