子集

whutshiliu Reply 3 weeks 4 days ago
#include<iostream> using namespace std; #define MAXN 18+1 void next_permutation(int n,int k,int num); int IsPrime(int n); int a[MAXN]= {0}; int main() { int t,n,k,num=1; cin>>t; while(t--) { cin>>n>>k; for(int i=0; i<n; i++) { cin>>a[i]; } next_permutation(n,k,num); num++; } } void next_permutation(int n,int k,int num) { int solution=0; for(int i=1; i<(1<<n); ++i) { int cnt=0,sum=0; for(int j=0; j<n; j++) { if(i&(1<<j)) { cnt++; sum += a[j]; } } if(cnt==k&&IsPrime(sum)) solution++; //cout<<endl; } cout<<"Case #"<<num<<": "<<solution<<endl; } int IsPrime(int n) { int res=1; for(int i=2; i*i<=n; i++) { if(n%i==0) res=0; } return res; }