j242 - 111北二1a.自然數的平方根

🔗 前往 ZeroJudge 原題

題目描述

題目要求將給定的自然數 n 分解成平方根形式，即找出 n = a * sqrt(b)，其中 a 和 b 都是整數，且 b 是不能被任何平方數整除的數。如果 n 是一個完全平方數，則輸出 a。如果 n 本身就是一個平方數，則輸出 sqrt(n)。

解題思路

這個問題的核心是將給定的數字進行質因數分解，並將所有平方因數提取出來。程式碼從 2 開始迭代到 sqrt(n)，對於每個 i，如果 n 可以被 ii 整除，則將 i 乘到 ba (代表平方根外的因數) 上，並將 n 除以 ii。這個過程重複進行，直到 n 不能被 i*i 整除。最後，如果 n 等於 1，則表示 n 已經完全分解，輸出 ba。如果 ba 等於 1，則表示 n 本身就是一個平方數，輸出 "sqrt(" + n + ")"。否則，輸出 ba + " sqrt(" + n + ")"。

複雜度分析

• 時間複雜度: O(sqrt(n))
• 空間複雜度: O(1)

程式碼

#include <iostream>
#include <cmath>
using namespace std;
int n;
long long ba=1;
int main(){
	cin >> n;
	for(int i=2;i<=sqrt(n);++i){
		while(n%(i*i)==0){
			ba*=i;
			n/=(i*i);
		}
	}
	if(n==1){
		cout << ba;
	}
	else if(ba==1){
		cout << "sqrt(" << n << ")";
	}
	else{
		cout << ba << " sqrt(" << n << ")"; 
	}
}