e653 - 10490 - Mr. Azad and his Son!!!!!

🔗 前往 ZeroJudge 原題

題目描述

題目要求判斷對於給定的正整數 k，計算出的數字 p = (2^(k-1))*(2^k - 1) 是否為完美數。如果 p 是完美數，則輸出 "Perfect: p!"。如果 p 不是完美數，但 k 是質數，則輸出 "Given number is prime. But, NO perfect number is available."。如果 p 不是完美數，且 k 不是質數，則輸出 "Given number is NOT prime! NO perfect number is available."。

解題思路

首先，題目給定的 p = (2^(k-1))*(2^k - 1) 是一個偶數，且 2^k - 1 是梅森質數時，p 才是完美數。因此，解題思路是：

1. 計算 p = (2^(k-1))*(2^k - 1)。
2. 判斷 p 是否為完美數。判斷方法是從 2 到 sqrt(p) 遍歷，如果 p 能被任何數字整除，則 p 不是完美數。
3. 如果 p 不是完美數，判斷 k 是否為質數。判斷方法是從 2 到 sqrt(k) 遍歷，如果 k 能被任何數字整除，則 k 不是質數。
4. 根據判斷結果輸出相應的訊息。

複雜度分析

• 時間複雜度: O(sqrt(p) + sqrt(k))，其中 p = (2^(k-1))*(2^k - 1)。由於 k <= 31，p 的大小是有限的，因此可以認為時間複雜度是 O(1)。
• 空間複雜度: O(k)，用於儲存 kas 陣列。由於 k <= 31，因此空間複雜度是 O(1)。

程式碼

#include <iostream>
#include <cmath>
using namespace std;
long long int kas[33];
int main(){
	int k;
	for(int i=1;i<33;++i)
		kas[i]=((1<<i)-1);
	while(cin >> k){
		if(k==0)break;
		bool ans=1,ak=1;
		for(int i=2,si=sqrt(kas[k]);i<=si;++i){
			if(kas[k]%i==0){
				ans=0;
				break;
			}
		}
		for(int i=2,ki=sqrt(k);i<=ki;++i){
			if(k%i==0){
				ak=0;
				break;
			}
		}
		if(ans)
			cout << "Perfect: " << kas[k]*(1<<k-1) << "!\n";
		else if(ak)
			cout << "Given number is prime. But, NO perfect number is available.\n";
		else
			cout << "Given number is NOT prime! NO perfect number is available.\n";
	}
}