algorithm - 双正方形 : counting numbers which are sums of two perfect squares

Question

来源:Facebook Hacker Cup Qualification Round 2011

双平方数是一个整数 X，可以表示为两个完全平方数的和。例如，10 是双正方形，因为 10 = 3² + 1²。给定 X，我们如何确定它可以写成两个平方和的方式的数量？比如10只能写成3² + 1²(我们不算1² + 3² 因为不同)。另一方面，25 可以写成 5² + 0² 或 4² + 3² .

你需要解决 0 ≤ X ≤ 2,147,483,647 的问题。

例子:

• 10 => 1
• 25 => 2
• 3 => 0
• 0 => 1
• 1 => 1

Answer 1

对数字 n 进行因式分解，并检查它是否具有奇数估值的质因数 p，使得 p = 3 (mod 4)。当且仅当 n 不是两个平方的和时才会发生。

解决方案的数量有一个封闭形式的表达式，涉及 n 的约数。参见 this, Theorem 3以获得准确的陈述。