c184 - 盈虧互補
題目描述
題目要求判斷給定的數字 n 是否為完全數，如果不是，則判斷是否存在一個數字 m，使得 n 和 m 互為友好數。如果存在，輸出 n 和 m 是友好數，否則輸出 n 沒有朋友。
解題思路
首先，計算 n 的真因數和。如果真因數和等於 n，則 n 是完全數。如果不是，則尋找一個數字 x，其真因數和等於 n。如果找到這樣的 x，則 n 和 x 是友好數。尋找 x 的過程是通過遍歷可能的因數來計算 x 的真因數和，並判斷其是否等於 n。
複雜度分析
- 時間複雜度: O(sqrt(n))
- 空間複雜度: O(1)
程式碼
#include <iostream>
#include <cmath>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n;
while (cin>>n,n!=0){
int x=1,y=1;
double sn=sqrt(n);
for(int i=2;i<=sn;i++){
if(n%i==0 && i!=sn) {
x+=i;
x+=n/i;
}
else if(n%i==0 && i==sn) x+=i;
}
if(x==n) cout << "=" << n << "\n";
else{
double sm=sqrt(x);
for(int i=2;i<=sm;++i){
if(x%i==0 && i!=sm) {
y+=i;
y+=x/i;
}
else if(x%i==0 && i==sm) y+=i;
}
if(y==n) cout << x << "\n";
else cout << "0\n";
}
}
}