洛谷 P1036 [NOIP2002 普及组] 选数

题目链接：https://www.luogu.com.cn/problem/P1036

题目描述

已知 个整数 ，以及 个整数 （）。从 个整数中任选 个整数相加，可分别得到一系列的和。例如当 ，， 个整数分别为 时，可得全部的组合与它们的和为：

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：。

输入格式

第一行两个空格隔开的整数 （，）。

第二行 个整数，分别为 （）。

输出格式

输出一个整数，表示种类数。

分析

题目要求求出，取 个数的和为质数的，有多少种选法？

首先对于 个数取k个数一共有 种选法（根据排列组合）。要求出和为质数的个数，需要对和是否为质数进行判断。

质数筛

是一种快速“筛”出2~n之间所有素数的方法。朴素的筛法叫埃氏筛（the Sieve ofEratosthenes，埃拉托色尼筛）

算法实现如下

// 判断是否为素数
bool is_prime(int num) {
    for (int i = 2; i <= num / i; i++)
        if (num % i == 0) return false;
    return true;
}

深搜

采用深搜来遍历每个组合

C++完整代码实现

#include <vector>
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

// 判断是否为素数
bool is_prime(int num) {
    for (int i = 2; i <= num / i; i++)
        if (num % i == 0) return false;
    return true;
}

// 求和函数
int sum(vector<int> nums) {
    int tmp = 0;
    for (int num: nums) {
        tmp += num;
    }
    return tmp;
}

vector<int> knum; // 记录数字组合
vector<bool> nxt; // 记录数字是否已经被访问
int n, k;
int cnt = 0; // count

// dfs 深搜，函数递归层数为 k + 1
void dfs(int *nums, int size,int statu) {
    if (size == k) {
        if (is_prime(sum(knum))) ++cnt;
        return;
    }
    for (int i = statu; i < n; ++i) {
        if (nxt[i]) continue;
        knum[size] = nums[i];
        nxt[i] = true;
        dfs(nums, size + 1,i);
        nxt[i] = false;
    }
}

int main() {
    cin >> n >> k;
    int nums[n];
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    nxt.resize(n, false);
    knum.resize(k);
    dfs(nums, 0,0);
    cout << cnt;
    return 0;
}