a254 - 畢氏‧三角‧製造
題目描述
題目要求計算給定一組木棍長度，最多可以製造出多少個「最約畢氏三角」。最約畢氏三角的定義是三邊長為正整數，滿足 a^2 + b^2 = c^2，且 a 和 b 的最大公因數為 1。木棍只能用於構成三角形的 a 和 b 邊，且每根木棍最多只能使用一次。
解題思路
程式碼使用貪心策略來尋找滿足畢氏定理且互質的木棍組合。首先，計算每個木棍長度的平方，儲存在 b 陣列中。然後，使用兩層迴圈遍歷所有可能的木棍組合。對於每對木棍，檢查它們是否都未被使用，以及它們的長度是否互質（使用 GCD 函數計算最大公因數）。如果滿足這些條件，則計算它們的平方和，並檢查該和是否為完全平方數。如果是，則將計數器 ans 增加 1，並將這兩根木棍標記為已使用。最後，輸出 ans 的值。
複雜度分析
- 時間複雜度: O(n^2 * sqrt(max_value))，其中 n 是木棍的數量，max_value 是木棍長度的最大值。兩層迴圈導致 O(n^2) 的複雜度，而計算平方根導致 O(sqrt(max_value)) 的複雜度。
- 空間複雜度: O(n)，用於儲存木棍長度和是否已使用的標記。
程式碼
#include <iostream>
#include <cmath>
using namespace std;
long long int a[201],b[201],n;
bool used[201];
int GCD(int a, int b) {
int buffer;
while (b)
buffer = a, a = b, b = buffer % b;
return a;
}
int main(){
cin.sync_with_stdio(false); cin.tie(0);
while(cin >> n){
for(int i=0;i<n;++i){
cin >> a[i];
b[i]=a[i]*a[i];
used[i]=0;
}
int ans=0;
for(int i=0;i<n;++i){
for(int j=i+1;j<n;++j){
if(used[i]==0&&used[j]==0&&GCD(a[i],a[j])==1){
long long int buffer=b[i]+b[j],sb=sqrt(buffer);
if ((sb * sb) == buffer){
++ans;
used[i]=used[j]=1;
}
}
}
}
cout << ans << "\n";
}
}