[NOIP2002-普及] 选数

题目描述

给定 $n$ 个整数 $x_1,\dots,x_n$ 和整数 $k$ （ $1\le n\le20$ ， $k<n$ ， $1\le x_i\le5\times10^6$ ），任选其中 $k$ 个（不计顺序），求和为素数的选法数。输入第一行 $n,k$ ，第二行 $x_1,\dots,x_n$ ；输出满足条件的种数。样例输入 4 3 / 3 7 12 19，样例输出 1（仅 $3+7+19=29$ 为素数）。

思路

递增下标 DFS 枚举全部 $\binom{n}{k}$ 个组合天然不重不漏，每个组合求和后试除到 $\sqrt S$ 判素（ $S\le10^8$ ），累加合法组合数即可。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 04:44
# update_at: 2026-10-02 04:44

import sys
from functools import cache
from itertools import combinations
from math import isqrt

SIEVE_LIMIT = 10**4  # 组合和 ≤ 20×5×10^6 = 10^8，试除只需到 √10^8 = 10^4


def primes_upto(limit: int) -> list[int]:
    """埃氏筛出 [2, limit] 内全部素数，判素时只试这些候选因子。"""
    sieve = bytearray([1]) * (limit + 1)
    sieve[0:2] = b"\x00\x00"
    for p in range(2, isqrt(limit) + 1):
        if sieve[p]:
            sieve[p * p :: p] = b"\x00" * ((limit - p * p) // p + 1)  # 从 p² 起标掉倍数
    return [p for p in range(2, limit + 1) if sieve[p]]


PRIMES = primes_upto(SIEVE_LIMIT)  # 1e4 内共 1229 个素数


@cache
def is_prime(m: int) -> bool:
    """试除判素：m ≤ 10^8 必有素因子 ≤ 10^4，故素数表已覆盖全部候选。"""
    if m < 2:
        return False
    return all(m % p for p in PRIMES if p * p <= m)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, k = next(data), next(data)
    xs = [next(data) for _ in range(n)]

    # 组合不关心顺序，itertools.combinations 恰好生成 C(n,k) 个下标递增的 k 元组，不重不漏；
    # @cache 让撞出相同和的组合（如全 1 数据）只判素一次。
    print(sum(is_prime(sum(chosen)) for chosen in combinations(xs, k)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 12:31
 * update_at: 2026-10-06 12:31
 */
/* roj 3513 [NOIP2002-普及] 选数 */
/* 递增下标 DFS 枚举所有选 k 个数的组合，求和并判断是否为素数。 */
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 25;

int n, k;
ll a[MAXN]; // 输入数组，单个 xi ≤ 5e6
ll ans;     // 和为素数的组合个数，最多 C(20,10) < 2e5 但用 ll 更省心

// 判断 x 是否为素数：只需试除到 sqrt(x)，x ≤ 1e8 故循环次数很小
bool is_prime(ll x) {
    if (x < 2) return false;
    for (ll i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

// dfs(dep, last, sum)：正在选第 dep 个数（从 1 开始），
// 上一个选中的下标是 last，当前已选数字的和是 sum
void dfs(int dep, int last, ll sum) {
    if (dep == k + 1) {
        // 已经选满 k 个数，判断和是否为素数
        if (is_prime(sum)) ans++;
        return;
    }

    // 下标递增保证组合不重不漏：第 dep 个数只能从 last+1 往后选。
    // 上界剪枝：之后还要选 k - dep 个数，下标 i 最多到 n - (k - dep)
    for (int i = last + 1; i <= n - (k - dep); i++) {
        dfs(dep + 1, i, sum + a[i]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    dfs(1, 0, 0); // 正在选第 1 个数，上一个下标是 0，当前和为 0
    cout << ans << "\n";
    return 0;
}

[NOIP2002-普及] 选数

目录

题目描述

思路

参考代码