倍数枚举统计每个约数能覆盖多少能力值，再把答案从大人数向小人数传播。
OJ: luogu
题目 ID: P1414
难度:普及+/提高
标签:最大公约数倍数枚举计数python
日期: 2026-07-16 19:20
题意
对每个 k=1..n，从能力值中选 k 个，使它们的 gcd 最大，输出这个最大值。
思路
若有至少 k 个能力值是 d 的倍数，就能从中选 k 个，它们的 gcd 至少为 d。因此枚举 d，累加 d,2d,... 的出现次数 count，说明 d 可供最多 count 人使用。
先令 answer[count] 记录恰好这个覆盖数下最大的 d。一个约数能覆盖 count 人，也一定能覆盖任意更少人数，所以再从 n-1 向 1 做：
text
answer[k]=max(answer[k],answer[k+1])Python 知识
- 两个
array('I')紧凑保存百万值域频次和至多一万项答案。 range(d,maximum+1,d)枚举d的全部倍数。- 逆序传播用
range(n-1,0,-1)。 map(str,answer[1:])转换后按行连接。/home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md：值域数组内存。/home/rainboy/mycode/hugo-blog/content/program_language/python/map_reduce_filter.md：倍数贡献累计。
代码
python
import sys
from array import array
def main():
data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]
values = data[1:]
maximum = max(values)
frequency = array("I", [0]) * (maximum + 1)
for value in values:
frequency[value] += 1
answer = array("I", [0]) * (n + 1)
for divisor in range(1, maximum + 1):
count = 0
for multiple in range(divisor, maximum + 1, divisor):
count += frequency[multiple]
if divisor > answer[count]:
answer[count] = divisor
for count in range(n - 1, 0, -1):
answer[count] = max(answer[count], answer[count + 1])
print("\n".join(map(str, answer[1:])))
if __name__ == "__main__":
main()cpp
/**
* P1414 又是毕业季II
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-07-27 00:00
* update_at: 2026-07-27 00:00
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10005;
const int MAXV = 1000005;
int freq[MAXV]; // 每个数的出现次数
int cnt[MAXN]; // cnt[k] = 能被 k 个数同时整除的最大值
int n, max_val;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
int x;
scanf("%d", &x);
++freq[x];
if (x > max_val) max_val = x;
}
// 对每个可能的约数 d，统计有多少个数是 d 的倍数
for (int d = 1; d <= max_val; ++d) {
int total = 0;
for (int m = d; m <= max_val; m += d)
total += freq[m];
// 如果有 total 个数能被 d 整除，则 cnt[total] = max(cnt[total], d)
if (total) cnt[total] = max(cnt[total], d);
}
// 后缀取最大：cnt[k] 至少是 cnt[k+1]
for (int k = n - 1; k >= 1; --k)
cnt[k] = max(cnt[k], cnt[k + 1]);
for (int k = 1; k <= n; ++k)
printf("%d\n", cnt[k]);
return 0;
}复杂度
设最大能力值为 V，时间复杂度
总结
把“选哪些人”反转为“某个候选 gcd 能整除多少能力值”，组合选择问题就变成了倍数计数。