几年前，我发现了一个有趣的编程问题：
“用n和1秒的时间限制找到n < 10^9的分区数为三个方格的总和。”
问题：有没有人知道如何用给定的约束来解决这个问题？
我认为它可以纯粹用渐近时间复杂度比O(n)更快吗？有一些聪明的数学方法还是代码优化工程问题？
我在https://oeis.org/A000164上找到了一些信息，但在FORMULA部分有一个O(n)-algo
（因为我们需要在MAPLE部分找到计算n-k^2的每个e(n-k^2)数的所有除数）和O(n)-algo。
是。首先将数字n - z^2分解为素数，将素数分解为高斯共轭，并找到不同的表达式来扩展和简化以得到a + bi，然后可以将其提升，a^2 + b^2。我们可以排除任何候选n - z^2包含具有奇数幂的形式4k + 3的素数。
这是基于将数字表示为高斯整数共轭。 (a + bi)*(a - bi) = a^2 + b^2。见https://mathoverflow.net/questions/29644/enumerating-ways-to-decompose-an-integer-into-the-sum-of-two-squares和https://stackoverflow.com/a/54839035/2034787