a768 - pD. 小蝦的煩惱
題目描述
題目給定一組整數，要求計算可以從這些整數中組成的直角三角形的數量。直角三角形的邊長必須滿足勾股定理：a^2 + b^2 = c^2。
解題思路
此題採用暴力解法。首先，將輸入的數字陣列進行排序。然後，使用兩層迴圈遍歷所有可能的 a 和 b 的組合。對於每一組 a 和 b，計算 c^2 = a^2 + b^2，並計算 c 的平方根。如果 c 的平方根是整數，則表示存在一個直角三角形，並且使用二分搜尋法在排序後的陣列中查找是否存在長度為 c 的邊。如果找到，則答案加一。
複雜度分析
- 時間複雜度: O(n^2 * log n)
- 空間複雜度: O(n)
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
long long int n[3001],target;
inline bool bs(int l,int r){
if(l>r)return 0;
int m=(l+r)>>1;
if(n[m]==target)
return 1;
else if(n[m]>target)
return bs(l,m-1);
return bs(m+1,r);
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int a,ans(0),i,j;
cin >> a;
for(i=0;i<a;++i)
cin >> n[i];
sort(n,n+a);
for(i=0;i<a;++i){
for(j=i+1;j<a;++j){
target=n[i]*n[i]+n[j]*n[j];
double c(target);
c=sqrt(c);
target=sqrt(target);
double c2(target);
if(c2!=c)continue;
if(bs(0,a))++ans;
}
}
cout << ans;
}