洛谷 P1414 又是畢業季II （多個數的最大公因數）

這道題其實不難，但是我想復雜了

我想的是把每個數質因數分解，然后每次就枚舉每個質因數

來求最小公倍數。

然后想了想這樣復雜度將會非常的大，肯定超時
然后看了題解發現不需要質因數分解，直接存因數的個數就好了
c[i]表示i這個因數出現的次數。
然后因為當k越小的時候答案越大（嚴格來說是大于等于），這是顯而易見的，當數少了
之后對最大公因數的限制就越少。
所以我們可以把因數從大到小枚舉，來求答案。

#include<cstdio>
#include<cmath>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1e6 + 10;
int c[MAXN], n, maxt, m, x;int main()
{scanf("%d", &n);_for(i, 1, n){scanf("%d", &x);maxt = max(maxt, x);m = sqrt(x + 0.5);_for(i, 1, m)if(x % i == 0){c[i]++;if(x != i * i) c[x/i]++;}}int ans = maxt;_for(i, 1, n){while(c[ans] < i) ans--;printf("%d\n", ans);}puts(""); for(int i = maxt; i >= 1; i--) printf("%d\n", c[i]); return 0;
}

?