algorithm - Representing an integer as the sum of four squares

Question

Given a positive integer m, find four integers a, b, c, d such that a^2 + b^2 + c^2 + d^2 = m in O(m^2 log m). Extra space can be used.

I can think of an O(m^3) solution, but I am confused about the O(m^2 logm) solution..

Answer 1

有一个经典的拉格朗日定理说每个自然数都是四个平方的和。

关于这个主题的维基百科页面提到有一个随机算法用于计算在 O(\lg^2 m) 时间内运行的表示（上面的所有建议都是 m 中的多项式，即它们在问题的大小上是指数的实例（因为数字 m 可以用 \lg m 位编码）。

顺便说一句，拉格朗日定理证明了带有加号和时间的整数的不可判定性（因为自然数是不可判定的，并且可以根据该定理在带有加号和时间的整数中定义）。

Answer 2

第一个提示：

将平方元素从 1 排序到 m^2 的复杂度是多少

第二个提示：

看看这篇文章以获得一些帮助：

休息时间，在 O(n^2) 中找到任何匹配毕达哥拉斯方程的三元组

第三个提示：

如果您需要更多帮助：（来自上一篇文章的 yi_H 回复）：

我猜 O(n^2 log n) 将是对数字进行排序，取任意两对 (O(n^2)) 并查看 c^2 = a^2 + b^ 的数字中是否有 c 2. 您可以使用二进制搜索来查找 c，即 O(log(n))。

作者：yi_H

现在比较 n 和 sqrt(m)

希望您能找到解决方案。