給定正整數 N,求有多少組整數 (A, B) 能滿足 A² + B² = N。注意 A、B 可為正、為負或為零,不同的正負組合都算不同的表示方式。例如 R(1)=4,因為 1=1²+0²=(-1)²+0²=0²+1²=0²+(-1)²。N 最大可達 10⁹。
輸入不超過 100 組測試數據,每組一個整數 N(N ≤ 10⁹)。對每個 N,輸出一行 R(N)。
樣例輸入:
2 6 10 25 65
樣例輸出:
4 0 8 12 16
以第四組為例,(A,B) 可以是 (0,5)、(0,-5)、(5,0)、(-5,0)、(3,4)、(3,-4)、(-3,4)、(-3,-4)、(4,3)、(4,-3)、(-4,3)、(-4,-3),共 12 組。
N 最大 10⁹,直接暴力枚舉 A、B 顯然不可行。關鍵在於利用對稱性:我們只需枚舉滿足 A > B ≥ 0 的情況,每一種有效組合實際對應 4 種變體——(A,B)、(A,-B)、(-A,B)、(-A,-B)。即使 B=0 時,(5,0)、(-5,0)、(0,5)、(0,-5) 也正好是 4 種。因此只要枚舉非負的一半,最後把結果乘以 4 即可。
枚舉時,A 的最大值為 √N,對每個 A 反推 B = √(N - A²),再驗證 A² + B² 是否等於 N 即可。
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
int main() {
int n,i,a,b,ma,res;
while(~scanf("%d",&n)) {
ma = sqrt(double(n)); // 最大的 a,a > b >= 0
res = 0;
for(a = 1; a <= ma; a++) {
b = sqrt(double(n - a*a));
if(a*a + b*b == n) res += 4; // a,b; a,-b; -a,b; -a,-b;
}
cout << res << endl;
}
return 0;
}
// 46MS 280K