目录
原题描述：
题目描述
题目背景
题目描述
输入格式
输出格式
样例
Input 1
Output 1
Input 2
Output 2
数据范围
主要思路：
代码code：
原题描述：
题目描述
题目背景
龙飞凤舞迎跨年，瑞雪飘飘送祝愿。愿你在新的一年，万事如意，福运连连。马上就到新年了，每个人都或多或少了收到了新年红包。
题目描述
小埋加了若干个群聊，小埋收集了一下若干个群聊中网友们获得的红包金额，一共收集到了 位网友的红包金额，小埋是个喜欢找点事干（太闲了），他想从中任意选取
位网友的红包金额，然后求出一个数
,满足这
位网友的红包金额都是
的倍数。说明这
位网友的财富度为
。小埋想知道这个财富度最大值是多少。小埋又菜又喜欢搞事情（找人帮忙）。小埋希望厉害的你能帮他解决这个问题。小埋在这里祝你新年快乐呦。
输入格式
第一行输入两个整数 ,
。
第二行输入 个整数
。
输出格式
输出一个整数，表示财富度最大值。
样例
Input 1
10 3
1 2 3 4 5 6 100 200 300 400Output 1
100Input 2
10 5
1 3 5 7 9 2 2 2 2 2 Output 2
2数据范围
| 测试点编号 | n≤ | |
|---|---|---|
| 1~6 | 20 | |
| 7~10 | 500 | |
| 11~20 |
主要思路：
还是来讲讲大部分人的想法：
有些人看到了n<=20，于是，他写了dfs或是二进制枚举，成功拿到了30分。
有些人看到了n<=100000,ai<=500,于是，他写了枚举因子，成功拿到了50分。
最后一种人，求知欲很高，要100分，于是就产生了这种方式：
分解因数+桶。
我们看一下，这道题是选k个数，使这k个数的gcd尽可能大。
我们可以将每个数分解因数，并存入桶。
用样例1解释一下。
1分解成1 tong[1]++;
2分解成1 2tong[1]++;tong[2]++;
3分解成1 3tong[1]++;tong[2]++;
4分解成1 2 4tong[1]++;tong[2]++;tong[4]++;
.
.
.
400分解成1 400 2 200 4 100 5 80 8 50 10 40 16 25 20 20 tong[前面的因子]++;
就是这样。
最后，从10^5枚举到1，如果发现tong[i]>=k就说明有k个数同时包含这个因子，就直接输出（我们从大到小枚举）
注意输入数据多，要用ios优化（用scanf的人不需要）
代码code：
#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[100010];
int tong[100010];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
for(int j=1;j*j<=a[i];j++)
{
tong[j]++;
if(j*j!=a[i])
{
tong[a[i]/j]++;
}
}
// cout<<tong[2]<<'\n';
}
// cout<<tong[2];
int ans=0;
// int x=*max_element(a+1,a+1+n);
for(int i=100010;i>=1;i--)
{
if(tong[i]>=k)
{
cout<<i;
return 0;
}
}
// cout<<ans;
return 0;
}
