这道题其实不难,但是我想复杂了
我想的是把每个数质因数分解,然后每次就枚举每个质因数
来求最小公倍数。
然后想了想这样复杂度将会非常的大,肯定超时
然后看了题解发现不需要质因数分解,直接存因数的个数就好了 c[i]表示i这个因数出现的次数。 然后因为当k越小的时候答案越大(严格来说是大于等于),这是显而易见的,当数少了 之后对最大公因数的限制就越少。 所以我们可以把因数从大到小枚举,来求答案。#include#include #include #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;}