chinacd wordpress第三性,制作网站公司首 荐乐云seo,重庆手机模板建站,淄博网站备案目录 原题描述#xff1a;
题目描述
题目背景
题目描述
输入格式
输出格式
样例
Input 1
Output 1
Input 2
Output 2
数据范围
主要思路#xff1a;
代码code#xff1a; 原题描述#xff1a;
题目描述
题目背景
龙飞凤舞迎跨年#xff0c;瑞雪飘飘送祝愿…目录 原题描述
题目描述
题目背景
题目描述
输入格式
输出格式
样例
Input 1
Output 1
Input 2
Output 2
数据范围
主要思路
代码code 原题描述
题目描述
题目背景
龙飞凤舞迎跨年瑞雪飘飘送祝愿。愿你在新的一年万事如意福运连连。马上就到新年了每个人都或多或少了收到了新年红包。
题目描述
小埋加了若干个群聊小埋收集了一下若干个群聊中网友们获得的红包金额一共收集到了 位网友的红包金额小埋是个喜欢找点事干太闲了他想从中任意选取 位网友的红包金额然后求出一个数 ,满足这 位网友的红包金额都是 的倍数。说明这 位网友的财富度为 。小埋想知道这个财富度最大值是多少。小埋又菜又喜欢搞事情找人帮忙。小埋希望厉害的你能帮他解决这个问题。小埋在这里祝你新年快乐呦。
输入格式
第一行输入两个整数 , 。
第二行输入 个整数。
输出格式
输出一个整数表示财富度最大值。
样例
Input 1
10 3
1 2 3 4 5 6 100 200 300 400
Output 1
100
Input 2
10 5
1 3 5 7 9 2 2 2 2 2
Output 2
2
数据范围 测试点编号n≤1~6207~1050011~20
主要思路
还是来讲讲大部分人的想法
有些人看到了n20于是他写了dfs或是二进制枚举成功拿到了30分。
有些人看到了n100000,ai500,于是他写了枚举因子成功拿到了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
#includebits/stdc.h
using namespace std;
int n,k;
int a[100010];
int tong[100010];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cinnk;for(int i1;in;i){cina[i];for(int j1;j*ja[i];j){tong[j]; if(j*j!a[i]){tong[a[i]/j];}}
// couttong[2]\n;}
// couttong[2];int ans0;
// int x*max_element(a1,a1n);for(int i100010;i1;i--){if(tong[i]k){couti;return 0;}}
// coutans;return 0;
}
