时间戳

首页 > 解决方案 > 将“n”划分为三个平方和的数量（快速算法）

algorithm - 将“n”划分为三个平方和的数量（快速算法）

问题描述

几年前，我发现了一个有趣的编程问题： “在时间限制为 1 秒 的情况下，找出三个平方和
的分区数。”nn < 10^9

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

我在https://oeis.org/A000164上找到了一些信息，但在 FORMULA 部分有一个O(n)-algo
（因为我们需要n-k^2为 compute 找到每个数字的所有除数e(n-k^2)）和O(n)MAPLE 部分中的 -algo。

标签： algorithmmathnumber-theory

解决方案

是的。首先将数字 ,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

推荐阅读