老师给每位同学评了一个能力值。于是现在问题变为，从n个学生中挑出k个人使得他们的默契程度（即能力值的最大公约数）最大。但因为节目太多了，而且每个节目需要的人数又不知道。老师想要知道所有情况下能达到的最大默契程度是多少。这下子更麻烦了，还是交给你吧~
PS：一个数的最大公约数即本身。
输入格式 第一行一个正整数n。
第二行为n个空格隔开的正整数，表示每个学生的能力值。
输出格式 总共n行，第i行为k=i情况下的最大默契程度。
输入输出样例 输入 #1
4 1 2 3 4输出 #1
4 2 1 1说明/提示
记输入数据中能力值的最大值为inf。
对于20%的数据，n<=5，inf<=1000
对于另30%的数据，n<=100，inf<=10
对于100%的数据，n<=10000，inf<=1e6
简单来说，给n个数，对从1到n的i，找到i个数使得最大公约数最大，依次输出这个最大公约数。看到这个题没想到什么特别好的解法，于是想到每次二分答案，然后依次验证。然后二分的答案会递减，所以还可以优化一下。但一想这起码是 O ( n 2 ) O(n^2) O(n2)的，就没浪费时间去写了，肯定过不了。
由于这是个n选k问题，有点像背包，就想dp。遍历n个数，用滚动数组f[k]表示n个数取k个的最大公约数，然后每次按取不取来推新的f[k]，但是仔细一想这样dp并不具有最优子结构。譬如78787，当前的7，计算f[3]时，如果取当前的7，之前的最大公约数是8，反而新的f[3]会变成1，所以直接否定。
然后就想到去挨个处理因子。对所有因子计算出现次数，但想到n次遍历寻找至少i次的最大因子又是1e6*10000的，就没多想。实际上我也知道最大因子一定是递减的，只需要一次遍历就可以找到所有的了。但就是没转过这个弯来，太菜了啊啊啊。。。有下面几个注意点：
只需要一个cnt数组记录因子次数就够了。输入的n个数没必要存了，当然存了也问题不大。要想到记录所有因子次数的时候，只需要 O ( n M A X V ) O(n\sqrt{MAXV}) O(nMAXV )次，也正是这个解法的复杂度。不知道为什么总是会忘记if x%k==0。。 #include <bits/stdc++.h> using namespace std; int n; int cnt[1000010]; int main(){ cin>>n; int inf=0; memset(cnt,0,sizeof(cnt)); for(int i=1;i<=n;i++){ int x; cin>>x; inf=max(inf,x); for(int k=1;k<=sqrt(x);k++){ if(x%k==0){ cnt[k]++; if(k*k!=x) cnt[x/k]++; } } } int now=inf; for(int i=1;i<=n;i++){ while(cnt[now]<i) now--; cout<<now<<endl; } return 0; }