一、准备知识
求一个数x的所有约数
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int c[N];
/**
* 功能：获取指定数x的所有约数
* @param x
*/
void ys(int x) {
for (int i = 1; i <= sqrt(x); i++)
//有约数
if (x % i == 0) {
c[i]++; //i作为约数的次数++
//记录另一个相对的约数
//x!=i*i 防止记录重复,如果是完全平方，就记一个，这个是大的
if (x != i * i) c[x / i]++;
}
}
int main() {
int x = 120;
//获得所有的约数
ys(x);
for (int i = 1; i <= x; i++)
for (int j = 1; j <= c[i]; j++) {
cout << i;
if (i < x) cout << "*";
}
return 0;
}
二、解题思路
思路：
(i)个数的公约数含义：(i)个数均含有某个约数，可以把所有数的约数全部求出来。
如果(i)个数均含有某个因数，那么这个因数必然是这(i)个数的公约数。
最大的就是它们的最大公约数。
总结：
1、(1)个数的最大公约数是它本身，这是本题给出的定义。下面的题解，也都是依照这个定义。
2、分解质因数+质因数个数 为(c[N]),(0<=i<N),(i)是指质因数，(c[i])是指质因数(i)同现的次数。
3、想找出在(n)个数中选择(i)个数时的最大公约数,这意味着： (1<=i<=n)
-
(c[m]>=i) 其中(m)表示因子(m)出现的次数大于等于(i)，选择了(i)个数字时，可能产生的公约数就是(m)。
-
那么，如何保证是最大呢？我们在计算每个数时，记录了最大约数(m),这是最大公约数的上限！
-
(while)循环，如果(m)的个数((c[m]))小于(i),表示这个数字(m)无法成为(i)个数字的约数。减小(1)继续尝试。
当找到第一个符合条件的数字时，它就是最大公约数。
(3)、每增大一个(i),即选择的数字越多，最大公约数只可能不变或变小,不可能变大，所以(m)值可以继续复用。这里很巧妙！
三、C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n; //n个同学的能力值
int m; //当前情况下可能的最大公约数
int c[N]; //每个约数i出现的次数c[i]
/**
* 功能：获取指定数x的所有约数
* @param x
*/
void ys(int x) {
for (int i = 1; i <= sqrt(x); i++)
//有约数
if (x % i == 0) {
c[i]++; //i作为约数的次数++
//记录另一个相对的约数
//x!=i*i 防止记录重复,如果是完全平方，就记一个，这个是大的
if (x != i * i) c[x / i]++;
}
}
int main() {
cin >> n;
//读入n个能力值
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
m = max(m, x); //记录目前最大能力值
//找出所有约数
ys(x);
}
//在n个数中选择i个数字，求可能产生的最大公约数。
for (int i = 1; i <= n; i++) {
while (c[m] < i) m--;
cout << m << endl;
}
return 0;
}