双正方形:计算两个完美正方形之和的数字

Question

资料来源:2011年Facebook黑客杯 资格赛

双平方数是整数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的除数.请参阅此定理3以获得精确的陈述.

Answer 2

这是我O(sqrt(n))复杂的简单答案

x^2 + y^2 = n
x^2 = n-y^2 
x = sqrt(n - y^2)

x应该是整数,所以(n-y^2)应该是完美的正方形.循环y=[0, sqrt(n)]并检查是否(n-y^2)是完美的正方形

伪代码:

count = 0;
for y in range(0, sqrt(n))
    if( isPerfectSquare(n - y^2))
         count++
return count/2