洛谷 P1036 选数

// 洛谷 P1036 选数 —— 第 ① 版：用「排列」去枚举（**答案偏大**）
//
// 输入：第一行 n k；第二行 n 个整数
// 输出：本该是「和为素数」的选法种数
//
// 这份为什么存在：这道题要「任选 k 个相加」，而手边最熟的枚举就是全排列 ——
// 于是很多人写出了一份**枚举排列**的代码：每一层挑一个还没用过的数，挑够 k 个就求和判素。
//
// ⚠ 它把同一组数**数了 k! 遍**：{3,7,19} 和 {7,3,19} 在它眼里是两回事，
//    可题目说的是「任选 k 个」—— 顺序根本不算数。
//    样例 n=4 k=3 的正确答案是 1，这一版会给 6（正好 3! = 6 倍）。
//
// ★★ 这个病和 [P1157 组合的输出] 是**同一个**：排列树天生会把同一个组合数很多遍。
//    治法也一样：**换成组合的枚举方式 —— 下一个数只从「上一个之后」挑**。
//    ⇒ 见第 ② 版那一行 for 的起点。

#include <bits/stdc++.h>
using namespace std;

int n, k;
int x[25];
bool used[25];
long long ans = 0;

bool isPrime(long long v) {
    if (v < 2) return false;
    for (long long i = 2; i * i <= v; i++) if (v % i == 0) return false;
    return true;
}

void dfs(int step, long long sum) {
    if (step == k) { if (isPrime(sum)) ans++; return; }
    for (int i = 0; i < n; i++) {
        if (used[i]) continue;
        used[i] = true;
        dfs(step + 1, sum + x[i]);
        used[i] = false;
    }
}

int main() {
    if (!(cin >> n >> k)) return 0;
    for (int i = 0; i < n; i++) cin >> x[i];
    dfs(0, 0);
    cout << ans << "\n";
    return 0;
}

// 洛谷 P1036 选数 —— 第 ② 版：组合枚举修好了，但 isPrime 把 1 当成了素数
//
// 输入 / 输出：同第 ① 版
//
// 这份为什么存在：第 ① 版的重复问题已经治好了（for 的起点改成 start），
// **但素数判断写错了一个边界**，而这个边界极容易漏。
//
//     bool isPrime(long long v) {
//         for (long long i = 2; i * i <= v; i++) if (v % i == 0) return false;
//         return true;                 // ⚠ v = 1 时循环一次都不进，直接返回 true
//     }
//
// ⇒ **1 被判成了素数。** 而 1 不是素数（素数的定义要求大于 1）。
//
// ⚠ 什么时候会咬到你：k 个数的和等于 1 —— 也就是 k = 1 且那个数是 1。
//    题面允许 x[i] >= 1、k >= 1，所以这是**合法输入**。
//    ⚠⚠ 但样例里没有这种数据，**样例一定是过的**。
//
// ★ 这一课比这道题大得多：
//   **判素数的函数，v < 2 那一行是本体，不是补丁。** 少写它的代价是一个只在特定数据上现形的 WA。

#include <bits/stdc++.h>
using namespace std;

int n, k;
int x[25];
long long ans = 0;

bool isPrime(long long v) {
    // ⚠ 少了一行 if (v < 2) return false;
    for (long long i = 2; i * i <= v; i++) if (v % i == 0) return false;
    return true;
}

void dfs(int step, int start, long long sum) {
    if (step == k) { if (isPrime(sum)) ans++; return; }
    for (int i = start; i < n; i++) dfs(step + 1, i + 1, sum + x[i]);
}

int main() {
    if (!(cin >> n >> k)) return 0;
    for (int i = 0; i < n; i++) cin >> x[i];
    dfs(0, 0, 0);
    cout << ans << "\n";
    return 0;
}

// 洛谷 P1036 选数 —— 第 ③ 版：组合枚举 + 正确的素数判断（正解）
//
// 输入：第一行 n k（1 <= n <= 20，k < n）；第二行 n 个整数（1 <= x[i] <= 5e6）
// 输出：和为素数的选法种数
//
// 两处关键，各治一个前面踩过的坑：
//
//   ① for 的起点是 start，不是 0          —— 选出来的下标天生递增 ⇒ 每个组合只数一次
//                                             （和 P1157 是同一招）
//   ② isPrime 的第一行是 if (v < 2)       —— 1 不是素数
//
// 工作量估一估（这一步应该在动手前做）：
//   最多 C(20,10) = 184 756 个组合，每个判一次素数最多 sqrt(20 * 5e6) ≈ 10^4 次试除。
//   ⇒ 最坏一亿多次除法，而绝大多数合数会被 2、3 这种小因子当场筛掉 ——
//     真正跑满 10^4 的只有那些真素数。1.5 秒的时限够用。
//
// ★ 「估一估再动手」这一步只要三秒钟，却能省掉「写完才发现要重写」的整轮返工。

#include <bits/stdc++.h>
using namespace std;

int n, k;
int x[25];
long long ans = 0;

bool isPrime(long long v) {
    if (v < 2) return false;                          // ★ 本体，不是补丁
    for (long long i = 2; i * i <= v; i++) if (v % i == 0) return false;
    return true;
}

// 已经选了 step 个，下一个只能从下标 start 往后挑，当前和是 sum
void dfs(int step, int start, long long sum) {
    if (step == k) { if (isPrime(sum)) ans++; return; }
    for (int i = start; i < n; i++) dfs(step + 1, i + 1, sum + x[i]);
}

int main() {
    if (!(cin >> n >> k)) return 0;
    for (int i = 0; i < n; i++) cin >> x[i];
    dfs(0, 0, 0);
    cout << ans << "\n";
    return 0;
}