将 `n` 划分为三个平方和的次数（快速算法）
Number of partition of `n` into sum of three squares (fast algorithm)
几年前我发现了一个有趣的编程问题：
"To find number of partition of n into sum of three squares with n < 10^9 and 1 second time limit."
问题：有谁知道如何在给定的约束条件下解决这个问题？
我认为它可以纯粹用渐近时间复杂度比 O(n) 快吗？有什么巧妙的数学方法还是代码优化工程问题？
我在 https://oeis.org/A000164 上找到了一些信息，但在公式部分
中有一个 O(n)-算法
（因为我们需要为计算 e(n-k^2) 找到每个 n-k^2 数字的所有除数）和 MAPLE 部分中的 O(n)-algo。
是的。先将数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 and
几年前我发现了一个有趣的编程问题：
"To find number of partition of n into sum of three squares with n < 10^9 and 1 second time limit."
问题：有谁知道如何在给定的约束条件下解决这个问题？
我认为它可以纯粹用渐近时间复杂度比 O(n) 快吗？有什么巧妙的数学方法还是代码优化工程问题？
我在 https://oeis.org/A000164 上找到了一些信息，但在公式部分
中有一个 O(n)-算法
（因为我们需要为计算 e(n-k^2) 找到每个 n-k^2 数字的所有除数）和 MAPLE 部分中的 O(n)-algo。
是的。先将数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 and