深搜常规题,其实不需要用unordered_map
,只是我一开始理解题目以为相同和被视为一种情况了。
有人看我再继续写。
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int ans, n, k, prime_range;
int a[25];
unordered_map<int, int> mp;
vector<int> primes;
void gen_prime(vector<bool>& isPrime) {
for (int i = 2; i <= prime_range; ++i) {
if (isPrime[i]) {
primes.push_back(i);
}
for (int j = 0; j < primes.size() && i * primes[j] <= prime_range; ++j) {
isPrime[i * primes[j]] = false;
if (i % primes[j] == 0)
break;
}
}
}
void dfs(int dep, int x, int sum) {
if (dep == k + 1) {
mp[sum]++;
return;
}
for (int i = x; i <= n - k + dep; ++i) {
dfs(dep + 1, i + 1, sum + a[i]);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
prime_range += a[i];
}
vector<bool> isPrime(prime_range + 1, true);
gen_prime(isPrime);
sort(a + 1, a + n + 1);
dfs(1, 1, 0);
for (auto [val, num] : mp) {
ans += isPrime[val] * num;
}
cout << ans;
}