h631 - 美麗人生

🔗 前往 ZeroJudge 原題

題目描述

題目要求判斷一個給定的正整數 n 是否為「醜數」。醜數的定義是，將其所有 2、3、5 因數都除盡後，結果為 1。如果滿足此條件，則輸出 "ugly"，否則輸出 "beautiful"。

解題思路

此題的核心在於判斷一個數是否僅包含 2、3、5 這三個質因數。程式碼透過迴圈不斷地將 n 除以 2、3、5，直到無法再被整除為止。最後，如果 n 等於 1，則表示原數僅包含 2、3、5 這三個質因數，為醜數；否則，表示原數包含其他質因數，為美麗數。

複雜度分析

• 時間複雜度: O(log n) (因為每次除以 2, 3, 5，n 的大小會呈指數級下降)
• 空間複雜度: O(1) (使用了常數級別的額外空間)

程式碼

#include <bits/stdc++.h>
using namespace std;
long long n;
int main(){
	cin >> n;
	while(n%2==0)n/=2;
	while(n%3==0)n/=3;
	while(n%5==0)n/=5;
	n==1?cout << "ugly":cout << "beautiful";
}