k376 - 求包含最大質因數的數

🔗 前往 ZeroJudge 原題

題目描述

題目要求從給定的 N 個數字中找出一個數字，使得該數字的最大質因數最大。如果有多個數字具有相同最大質因數，則輸出這些數字中最大的那個。

解題思路

對於每個輸入的數字，我們需要找到它的最大質因數。可以通過迭代的方式，從 2 開始到該數字本身，檢查每個數字是否為其因數。如果找到一個因數，則不斷除以該因數，直到不能再被整除。在除的過程中，記錄下最大的因數，這個最大的因數就是該數字的最大質因數。

然後，我們維護兩個變數：ap 記錄目前找到的最大質因數，ans 記錄目前找到的具有最大質因數的數字。對於每個數字，如果它的最大質因數大於 ap，或者最大質因數等於 ap 但該數字本身大於 ans，則更新 ap 和 ans。

最後，輸出 ans。

複雜度分析

• 時間複雜度: O(N * M)，其中 N 是輸入數字的個數，M 是最大輸入數字的大小。對於每個數字，我們最多需要迭代到該數字本身來尋找質因數。
• 空間複雜度: O(1)，我們只使用了幾個常數大小的變數。

程式碼

#include <iostream>
using namespace std;
int n,ans,x,ap;
int main(){
	cin >> n;
	while(n--){
		cin >> x;
		int mp=1,y=x;
		for(int i=2;i<=x;++i){
			while(x%i==0){
				mp=max(mp,i);
				x/=i;
			}
		}
		if(ap<mp||(ap==mp&&y>ans)){
			ans=y;
			ap=mp;
		}
	}
	cout << ans;
}