题解 P1414 【又是毕业季II】

· · 题解

接着lzn大人的思路把题解编下去（略有不同）。
我们想到，k个数的公约数含义就是这k个数均含有某个因数，如果我们把所有数的因数全部求出来，发现有k个数均含有某个因数，那么这个数必然是这k个数的公约数。其中找出最大的就是它们的最大公约数。
每个数分解因数，c[i]表示i作为因子的次数。 对于答案i，c[x]>i的p可以作为答案。
可以发现i的答案一定大于等于i+1的答案。
扫一遍找答案行了。
lzn大人已经把思路讲的很明白了，请允许我把代码补上QwQ 

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n,t=0,c[1000010];
//c[i]表示i作为因子的次数
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x; cin>>x;
        t=max(t,x);
        //记录目前最大能力值
        int m=sqrt(x);
        //能力值的开方
        for(int i=1;i<=m;i++)
            if(x%i==0)
            //有约数
            {
                c[i]++;
                //i作为因子的次数++
                if(x!=i*i) c[x/i]++;
                //如果x不是i的平方，x/i也是x的因子
                //如果x是i的平方只记录i作为一次因子
            }
    }
    int x=t;
    for(int i=1;i<=n;i++)
    {
        while(c[x]<i) x--;
        //找出最大的默契值（本题专有名词好烦QwQ）
        cout<<x<<endl;
        //输出
    }
    return 0;
    //华丽丽的结束
}