1

完美平方数的例子是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 ？

4

1 回答 1

3

很容易注意到完美正方形之间的区别：

0   1   4   9   16   25   ...
|___|___|___|___|_____|
  |   |   |   |    |
  1   3   5   7    9

所以我们有：

answer = 0;
for(i = 1; answer <= 10^20; i = i + 2)
    answer = answer + i;
    print(answer);
}

由于您想要直到 x 之前的所有完美平方，因此时间复杂度将为 O(sqrt(x))，对于 x = 10^20，其平方为 10^10，这可能会很慢。

于 2020-04-10T21:18:16.030 回答