1775 - 选数
已知 n 个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：
3＋7＋12=22 3＋7＋19＝29 7＋12＋19＝38 3＋12＋19＝34。
现在，要求你计算出和为素数共有多少种。
例如上例，只有一种的和为素数：3＋7＋19＝29）。
Input
键盘输入，格式为：
n , k （1<=n<=20，k＜n）
x1,x2，…,xn （1<=xi<=5000000）
Output
屏幕输出，格式为：
一个整数（满足条件的种数）。
Examples
Input
4 3 3 7 12 19
Output
1
Solution C++
#include<iostream> #include<cmath> using namespace std; int n,m,i,ans=0,s=0,a[21],f[10001]={0},p[2000]; void get()//建立10000以内的素数表 { int i,j,k=0; f[1]=1; for(i=2;i<=int(sqrt(10000));i++) if(f[i]==0) { p[k++]=i; for(j=i*i;j<=10000;j+= i)f[j]=1; } } void work(int s) { int i; if(s<=10000){if(f[s]==0)ans++;}//直接判断 else{ for(i=0;p[i]*p[i]<=s;i++)if(s%p[i]==0)return; ans++; } } void search(int d,int pre)//d选的个数,pre前一次选的编号 { int i; if(d>m)work(s); else for(i=pre+1;i<=n-(m-d);i++) { s+=a[i]; search(d+1,i); s-=a[i]; } } int main() { cin>>n>>m; for(i=1;i<=n;i++)cin>>a[i]; get(); search(1,0); cout<<ans; }