原题链接:https://www.luogu.com.cn/problem/P1414
题意解读:有n个数,从其中选k个数,k=1, 2, 3......n,使得这k个数的gcd最大。
解题思路:
如何求k个数的最大公约数呢?暴力法肯定不行。
可以从1到n枚举这个最大公约数i,看是否有>=k个数的因数是i
具体来说,用桶数组存放所有整数,a[x]表示x的个数
对于一个i,对其乘以1,2,3...,只要结果在a中存在,则累加个数到cnt
记录有多少个整数的因数是i,b[cnt] = i
那么要统计k个数的最大公约数的最大值,就统计个数>=k的因数的最大值,max(b[k],b[k+1]......)
举例:
如果b[k] = 10, b[k+1] = 20
显然k + 1个数的因数一定也是k个数的因数,k个数的因数最大值应该是20
只需要逆向处理一遍b,用后一个数和前一个数的因数比较,用较大的更新前一个数的因数:
for(int k = n - 1; k>= 1; i--) b[k] = max(b[k], b[k + 1]);
再输出b[k]对应结果即可,k=1...n
100分代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 10005, INF = 1000001;
int n, x;
int a[INF], b[N];
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> x, a[x]++;
for(int i = 1; i < INF; i++)
{
int cnt = 0;
for(int j = i; j < INF; j += i)
{
if(a[j]) cnt += a[j];
}
b[cnt] = i;
}
for(int k = n; k >= 1; k--) b[k] = max(b[k], b[k + 1]);
for(int k = 1; k <= n; k++) cout << b[k] << endl;
return 0;
}
标签:cnt,int,洛谷题,个数,P1414,II,因数,INF From: https://www.cnblogs.com/jcwy/p/18136168