表示整数的四个正方形

Question

给定一个正整数m，总和发现四个整数a，b，c，d这样a^2 + b^2 + c^2 + d^2 = m在O(m^2 log m)。可以使用额外的空间。

我能想到的O(m^3)解决方案，但我困惑的O(m^2 logm)解决方案..

Answer 1

第一个暗示：

什么是排序平方elemnt的复杂度从1到平方公尺

二提示：

看一看这个帖子一些帮助：

Break time, find any triple which matches pythagoras equation in O(n^2)

三提示：

如果您需要更多的帮助：（从yi_H响应在以前的帖子）：

我想为O（n^2 log n）的将排序的数字，采取任何两个 对（O（n^2）），并查看是否有c的数量为c^2 = a^2 + b^2。您可以使用二分查找来查找c，即 O（log（n））。

作者：yi_H

现在比较n和开方（M）

希望你能弄清楚这个解决方案。

Answer 2

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

关于此主题的Wikipedia页面提到，存在用于计算在O（\ lg^2 m）时间内运行的表示的随机算法（以上所有建议都是以m为单位的多项式，即它们在问题实例的大小（因为数字m可以以l m位为单位进行编码）

拉格朗日定理证明了带加号和时间的整数的不可判定性（因为自然是不可判定的，并且可以是定义在整数加上和时间，凭借定理）