您现在的位置: IOS教程網 >> IOS系統 >  >> iOS 程式開發 >> iOS 開發綜合

HDU 3835 R(N):加點思維的暴力枚舉

編輯:iOS 開發綜合

題目大意

給定正整數 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 即可。

AC 代碼

#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
  1. 上一篇文章:
  2. 下一篇文章:
蘋果刷機越獄教程| IOS教程問題解答| IOS技巧綜合| IOS7技巧| IOS8教程
Copyright © IOS教程網 All Rights Reserved