洛谷 1414 数学题 水题

---

---

其实刚开始做这道题的时候是有点虚的，想到了从因数下手的大概思路，但是O(n * sqrt(inf))的复杂度略有些吓人，所幸最后A了。。。最大的点40ms，数据还是比较良心的。。

题解：

看到题目需要多次求gcd，应该能够想到分解因数，从(1, sqrt(n))统计因数数量，用P[i]记录因子中有i的数的数量有多少个，输出时j 从inf到1枚举p[j]，i从1到n枚举答案，存在合法即输出

#include 
    
     #include 
     
      #include 
      
       #include 
       
        const int maxn = 1e6 + 10;int n;int x;int p[maxn];int main () {      scanf("%d", &n);    for (int i = 1; i <= n; i++) {        scanf("%d", &x);        int searchEnd = sqrt(x);        for (int j = 1; j <= searchEnd; j++) {            if (x % j == 0) {                p[j]++;                if (j * j == x) continue;                p[x / j]++;            }        }     }    int j = maxn;    p[1] = 100000;    //for (int i = 1; i <= 100; i++) printf("%d ", p[i]);    for (int i = 1; i <= n; i++) {        while (p[j] < i) j--;        printf("%d\n", j);    }    return 0;}