题解：P1036 [NOIP 2002 普及组] 选数

AFO_kunkun127 · 2025-02-28 13:11:09 · 题解

题目分析

题目要求从给定的 n 个整数中选出 k 个数，使得它们的和是一个素数。需要计算所有可能的选数方案中满足条件的方案数。

解题思路

考虑使用 DFS。递归生成所有可能的组合。start 表示当前选择的起始位置，sum 表示当前组合的和，step 表示已经选择的数的个数。对于每一种组合，计算它们的和，并判断这个和是否是素数。如果和是素数，那么答案加一。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, k, cnt, a[25];

bool is_prime(int x) 
{
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++) if (x % i == 0) return false;
    return true;
}

void dfs(int start, int sum, int step) 
{
    if (step == k) 
    {
        if (is_prime(sum)) cnt++;
        return;
    }
    for (int i = start; i <= n; i++) dfs(i + 1, sum + a[i], step + 1);
    return ; 
}

int main() 
{
    cin >> n >> k; 
    for (int i = 1; i <= n; i++) cin >> a[i];
    dfs(1, 0, 0);
    cout << cnt << endl;
    return 0;
}