d085 - 根號運算
題目描述
題目要求輸入一串數字，對於每個數字計算其平方根，並將結果簡化輸出。如果平方根是整數，則直接輸出整數。如果平方根不是整數，則將其表示為 a√b 的形式，其中 a 是平方根中可以提取的最大平方因子，b 是提取平方因子後的剩餘因子。如果輸入為負數，則在結果中加入 i。
解題思路
程式碼首先讀取輸入的數字 a。如果 a 是負數，則將其轉換為正數，並在簡化平方根後在結果中加入 i。然後，程式碼迭代從 2 到 sqrt(a) 的所有數字，檢查是否可以從 a 中提取平方因子。如果可以，則將 a 除以該平方因子，並將 b 乘以該因子的平方根。最後，程式碼根據 b 的值輸出簡化後的平方根。如果 b 為 1，則輸出空值。如果 a 為 0 或 1，則直接輸出 a。
複雜度分析
- 時間複雜度: O(sqrt(n))，其中 n 是輸入數字的大小。因為迴圈迭代到 sqrt(a)。
- 空間複雜度: O(1)，程式碼只使用了常數級別的額外空間。
程式碼
#include <iostream>
#include <cmath>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int a;
while(cin >> a){
if(a<0){
a*=-1;
int b=1;
for(int i=2;i<=sqrt(a);i++){
if(a%(i*i)==0){
a/=i*i;
b*=i;
i=1;
}
}
if(b!=1){
cout << b;
}
if(a!=1)
cout << "_/" << a << "i\n";
else
cout << "i\n";
}
else if(a==0||a==1){
cout << a << "\n";
}
else{
int b=1;
for(int i=2;i<=sqrt(a);i++){
if(a%(i*i)==0){
a/=i*i;
b*=i;
i=1;
}
}
if(b!=1){
cout << b;
}
if(a!=1)
cout << "_/" << a << "\n";
else
cout << "\n";
}
}
}