关于公因子的讨论

这类题其实就想说个优化：枚举倍数...

可有讲O（n）优化成logn的...

记得下次再看到这类题直接枚举倍数就可以了；

贴两道水体：

#include<bits/stdc++.h>
using namespace std;
const int N=1010000;
int n,o2,f[N],s;//s表示当前输出到哪个数了... 
inline int read()
{
    int x=0,ff=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') ff=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*ff;
}
inline void put(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) put(x/10);
    putchar(x%10+'0');
}
int main()
{
    freopen("group.in","r",stdin);
    freopen("group.out","w",stdout);
    n=read();
    for(register int i=1;i<=n;++i)
    {
        int x=read();
        o2=max(o2,x),f[x]++;
    }
    for(register int i=o2;i>=1;--i) //枚举所有因子... 
    {
        int cnt=0;
        for(register int j=1;j*i<=o2;++j)  //枚举倍数... 
            if(f[i*j]) cnt+=f[i*j];
        for(register int j=1;j<=cnt-s;++j) put(i),puts("");//输出. 
        if(cnt>=s) s+=cnt-s;               //如果这个因子输出过，则修改输出到哪个数了... 
        if(s>=n) break;
    }
    return 0;
}

#include<bits/stdc++.h>
#define max(a,b) (((a)>(b)?(a):(b)))
using namespace std;
const int N=1010000;
int n,K,f[N],o;
inline int read()
{
    int x=0,ff=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') ff=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*ff;
}
inline void put(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) put(x/10);
    putchar(x%10+'0');
}
int main()
{
    freopen("1.in","r",stdin);
    n=read();K=read();
    if(K==0) {printf("0");return 0;}
    for(register int i=1;i<=n;++i)
    {
        int x=read();o=max(o,x);
        f[x]++;
    }
    for(register int i=o;i>=1;--i)
    {
        int cnt=0;
        for(register int j=1;j*i<=o;++j) if(f[i*j]) cnt+=f[i*j];
        if(cnt>=K) {put(i);return 0;}
    }
    return 0;
}

......