algorithm - `n` 分成三平方和的分区数(快速算法)

Question

几年前我发现了一个有趣的编程问题:
“用 n 和 1 秒的时间限制将 n < 10^9 分成三个平方和的分区数。”

问题:有谁知道如何在给定的约束条件下解决这个问题？
我认为它可以纯粹用比 O(n) 更快的渐近时间复杂度来完成。仅有的？是否有一些聪明的数学方法或者是代码优化工程问题？

我在 https://oeis.org/A000164 上找到了一些信息, 但有一个 O(n) -公式部分的算法
(因为我们需要找到每个 n-k^2 数字的所有除数以计算 e(n-k^2) )和 O(n) -MAPLE 部分的算法。

Answer 1

是的。先将数n - z^2因式分解成质数，将质数分解成高斯共轭，再找不同的表达式展开化简得到a + bi，可以然后被提升，a^2 + b^2。我们可以排除任何包含形式为 4k + 3 且具有奇次幂的素数的候选 n - z^2。

这是基于将数字表示为高斯整数共轭。 (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