d306 - 10193 - All You Need Is Love
題目描述
題目要求判斷兩個二進位字串轉換成的十進位數是否互質。如果它們的最大公因數為 1，則輸出 "Love is not all you need!"，否則輸出 "All you need is love!"。
解題思路
題目描述中的「愛的算命機」實際上是一個障眼法。關鍵在於理解題目最終的要求是判斷兩個數是否互質。因此，只需要將輸入的二進位字串轉換為十進位數，然後計算它們的最大公因數 (GCD)。如果 GCD 為 1，則表示它們互質，否則不互質。程式碼中使用了輾轉相除法來計算 GCD。
複雜度分析
- 時間複雜度: O(log(min(x, y)))，其中 x 和 y 是兩個轉換後的十進位數。這是因為 GCD 的計算使用輾轉相除法，其時間複雜度與輸入數字的位數成對數關係。
- 空間複雜度: O(1)，程式碼只使用了常數級別的額外空間。
程式碼
#include <iostream>
using namespace std;
int GCD(int a, int b){
if (b)
while((a %= b) && (b %= a));
return a + b;
}
int main(){
string a,b;
int t,x,y;
cin >> t;
for(int c=1;c<=t;++c){
cin >> a >> b;
x=0,y=0;
for(int i=0,al=a.length();i<al;++i){
x*=2;
x+=a[i]-'0';
}
for(int i=0,al=b.length();i<al;++i){
y*=2;
y+=b[i]-'0';
}
cout << "Pair #" << c << ": ";
if(GCD(x,y)!=1)
cout << "All you need is love!\n";
else
cout << "Love is not all you need!\n";
}
}