解题思路

这道题目要求我们在一组给定的数字中，找出具有最大质因数的那个数字。如果有多个数字的最大质因数相同，则选择最先出现的那个数字。为了高效解决这个问题，我们可以采用以下步骤：

1. 预处理最大质因数表

首先，我们需要预处理一个数组mpf（max prime factor），其中mpf[i]表示数字i的最大质因数。这一步是关键，因为它能让我们在后续查询中快速获取任意数字的最大质因数。

• 初始化：将mpf数组初始化为0。
• 处理偶数：所有偶数的最小质因数是2，因此我们可以先将所有偶数的mpf值设为2。
• 处理奇数：对于每个奇数i，如果mpf[i]仍为0，说明i是质数。然后，我们将i的所有倍数j的mpf值设为i，因为i是这些数的一个质因数，且对于未设置过的数来说，i就是它们的最大质因数。

2. 处理输入数据

预处理完成后，我们可以开始处理输入数据：

• 读取数字的数量n。
• 逐个读取每个数字，并比较它们的最大质因数。
• 维护一个变量max_val，记录当前找到的最大质因数对应的数字。如果有更大的质因数出现，则更新max_val。

3. 输出结果

最后，输出max_val，即具有最大质因数的数字。

方法选择

• 筛法预处理：使用埃拉托斯特尼筛法的变种来预处理每个数字的最大质因数。这种方法的时间复杂度接近线性，能够高效处理大量数据。
• 直接比较：预处理完成后，直接比较每个数字的最大质因数，确保在O(1)时间内获取每个数字的最大质因数。

解决代码

#include <iostream>
#include <cstring>
using namespace std;

#define MAXN 20000

/* mpf[i]表示i的最大质因数 */
int mpf[MAXN + 1];

void maketabel(int n) {
    int i, j;
    
    memset(mpf, 0, sizeof(mpf));
    
    mpf[0] = 0;
    mpf[1] = 1;
    
    /* 所有偶数的最小质因数为2 */
    for (i = 2; i <= n; i += 2)
        mpf[i] = 2;
    
    /* 处理奇数，i为素数时更新其倍数的最大质因数 */
    for (i = 3; i <= n; i += 2)
        if (0 == mpf[i])
            for (j = i; j <= n; j += i)
                mpf[j] = i;
}

int main() {
    int n, max_val, val, i;
    
    maketabel(MAXN);
    
    while (cin >> n) {
        cin >> val;
        max_val = val;
        
        for (i = 2; i <= n; ++i) {
            cin >> val;
            if (mpf[val] > mpf[max_val])
                max_val = val;
        }
        
        cout << max_val << endl;
    }
    
    return 0;
}

代码解释

1. 预处理函数maketabel：

   • 初始化mpf数组为0。
   • 设置所有偶数的mpf值为2。
   • 对于每个奇数i，如果mpf[i]为0，则i是质数，将i的所有倍数的mpf值设为i。

2. 主函数main：

   • 调用maketabel预处理最大质因数表。
   • 读取输入的数字数量n。
   • 逐个读取数字，并比较它们的最大质因数，更新max_val。
   • 输出max_val，即具有最大质因数的数字。

标程

#include <iostream>
#include <cstring>
using namespace std;

#define MAXN 20000

/* 若mpf[i] = x，则x为i的最大因子（素数） mpf = maxprimefactor */
int mpf[MAXN + 1];

void maketabel(int n) {
	int i, j;
	
	memset(mpf, 0, sizeof(mpf));
	
	mpf[0] = 0;
	mpf[1] = 1;
	
	/* 对于偶数，令其因子暂时为２ */
	for (i = 2; i <= n; i += 2)
		mpf[i] = 2;
	
	/* 对于素数i，设置j=k*i的暂时因子为i */
	for (i = 3; i <= n; i += 2)
		if (0 == mpf[i])
			for (j = i; j <= n; j += i)
				mpf[j] = i;
}

int main() {
	int n, max_val, val, i;
	
	maketabel(MAXN);
	
	while (cin >> n) {
		cin >> val;
		max_val = val;
		
		for (i = 2; i <= n; ++i) {
			cin >> val;
			if (mpf[val] > mpf[max_val])
				max_val = val;
		}
		
		cout << max_val << endl;
	}
	
	return 0;
}