k个数的公约数的含义是这k个数中均含有某个因数， 因此我们只需把所有数的因数求出来，发现有k个数均含有某个因数，那么这个数必然是这k个数的公约数
因此此题的思路就是求出每个数的因子，并存储每个因子出现的次数。最后搜索这个数组就行 题目还保证了单调性
#include<iostream> #include<string> #include<cmath> #include<cstring> #include<vector> #include<map> #include<set> #include<algorithm> #include<queue> #include<stack> #include<list> #include<sstream> #include<cstdio> #define INF 0x3f3f3f3f const int maxn = 1e6 + 5; const double PI = acos(-1.0); typedef long long ll; typedef unsigned long long ull; using namespace std; int n; int c[maxn]; int Max; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); Max = max(Max, x); int m = sqrt(x); for (int i = 1; i <= m; i++) { if (x % i) { c[i]++; if (x != i * i) c[x / i]++; } } } int x = Max; for (int i = 1; i <= n; i++) { while (c[x] < i) x--; printf("%d\n", x); } return 0; }