AcWing 5491. 选数
原题链接
简单
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static int n;
static int k;
static int[] a;
static long sum;
static int cnt;
public static void main(String[] args) throws Exception {
String[] strs = br.readLine().split(" ");
n = Integer.parseInt(strs[0]);
k = Integer.parseInt(strs[1]);
strs = br.readLine().split(" ");
a = new int[n + 1];
for (int i = 1; i <= n ; i++) {
a[i] = Integer.parseInt(strs[i - 1]);
}
dfs(1,0);
System.out.println(cnt);
}
// x 代表选了几个数
public static void dfs(int u, int x) {
if(x >= k) {
for(int i = 2 ; i <= sum / i ; i ++ ) {
if(sum % i == 0) return;
}
cnt ++;
return;
}
for(int i = u; i <= n; i ++) {
sum += a[i];
dfs(i + 1,x + 1);
sum -= a[i];
}
}
}