纯粹思维题
时间复杂度O(nlogn)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, cnt[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)// 把每一个数的个数记录一下
{
int x;
scanf("%d", &x);
cnt[x] ++;
}
int res = 1;
for (int d = 2; d <= N; d ++)//枚举公约数d
{
int s = 0;
for(int j = d; j <= N; j += d)
s += cnt[j];
res = max(res,s);
}
printf("%d", res);
return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
调和级数是各项倒数为等差数列的级数,各项倒数所成的数列(不改变次序)为等差数列。从第2项起,它的每一项是前后相邻两项的调和平均,故名调和级数。
稍微写一下整体思路
1.先说题目意思: 给你 n 个数,让你一次挑出尽可能多的数,最大是多少?(挑数要求:这些数的最大公约数大于1)
2.提前记录每一个数出现的次数(因为数据最大1e5)
3.因为最大公约数最大是数据最大值,从2遍历到1e5,暴力枚举所有最大公约数;//每个公约数作为选数算一次选择,取最大值
例如 2 3 4 6 8 9 10 12 中两个序列中都出现了6,12,那么当枚举公因数2时,6 12都可以选中,当枚举
3时, 6,12如果出现,也要计算;
4.那么当枚举到某一个因数时,从d—N(每次+d)遍历每一个满足该最大共约数的数,加和;