洛谷P又是毕业季2（数学数论，找规律，公约数）

题目链接：https://www.luogu.org/problemnew/show/P1414

理解公约数本质，才能求出来。

最后输出答案的时候，要发现它递减的规律才能做出来完成这道题。（卡在这好久QAQ）

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cmath>
 4 using namespace std;
 5 const int maxn=1e6+5;
 6 int c[maxn];
 7 int n,Max;
 8 
 9 int main()
10 {
11     cin>>n;
12     for(int i=1;i<=n;i++)
13     {
14         int x; 
15         cin>>x;
16         Max=max(Max,x); //记录目前最大能力值
17         
18         int m=sqrt(x);
19         for(int i=1;i<=m;i++)
20         {
21             if(x%i==0)
22             {
23                 c[i]++; //i作为因子的次数++
24                 if(x!=i*i) c[x/i]++; //平方只记一次
25             }
26          }
27     }
28     
29     //for(int i=1;i<=t;i++) cout<<i<<' '<<c[i]<<endl;
30     int x=Max;
31     for(int i=1;i<=n;i++)
32     {
33         while(c[x]<i) x--; //找出最大的默契值
34         cout<<x<<endl;
35     }
36     return 0;
37 }

完。