P1036 选数

admin

https://www.luogu.org/problemnew/show/P1036
题目描述
已知 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）。

输入输出格式
输入格式：
键盘输入，格式为：

n , k （1<=n<=20，k＜n）

x1,x2，…,xn （1<=xi<=5000000）

输出格式：
屏幕输出，格式为：

一个整数（满足条件的种数）。

输入输出样例
输入样例#1：
4 3
3 7 12 19
输出样例#1：
1

弑魔者魔眼

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. int a[30];
   
4. bool check(int x)
   
5. {
   
6.         for(int i=2;i*i<=x;i++)
   
7.         if(x%i==0) return 0;
   
8.         return 1;
   
9. }
   
10. 
    
11. int main()
    
12. {
    
13.         int n,k,ans=0;
    
14.         cin>>n>>k;
    
15.         for(int i=0;i<n;i++) cin>>a[i];
    
16.         int U=1<<n;
    
17.         for(int S=0;S<U;S++)
    
18.         if(__builtin_popcount(S)==k)
    
19.         {
    
20.                 int sum=0;
    
21.                 for(int i=0;i<n;i++)
    
22.                 if(S&(1<<i)) sum+=a[i];
    
23.                 if(check(sum)) ans++;
    
24.         }
    
25.         cout<<ans;
    
26.         return 0;
    
27. }

复制代码

朱品屹

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. int a[25],aa[25],n,k,x=0,num=0;
   
4. bool b[25];
   
5. bool isprime(int x)
   
6. {
   
7.         for(int i=2;i<=sqrt(x);i++)
   
8.                 if(x%i==0)
   
9.                         return 0;
   
10.         return 1;
    
11. }
    
12. void dfs(int i)
    
13. {
    
14.         if(i>k)
    
15.         {
    
16.                 x=0;
    
17.                 for(int i=1;i<=k;i++)
    
18.                         x+=a[aa[i]];
    
19.                 if(isprime(x))
    
20.                         num++;
    
21.                 //cout<<a[aa[1]]<<' '<<a[aa[2]]<<' '<<a[aa[3]]<<' '<<x<<' '<<num<<endl;
    
22.         }
    
23.         else
    
24.         {
    
25.                 for(int j=aa[i-1]+1;j<=n;j++)
    
26.                 {
    
27.                         if(b[j]==1)
    
28.                         {
    
29.                                 aa[i]=j;
    
30.                                 b[j]=0;
    
31.                                 dfs(i+1);
    
32.                                 b[j]=1;
    
33.                         }
    
34.                 }
    
35.         }
    
36. }
    
37. int main()
    
38. {
    
39.         cin>>n>>k;
    
40.         for(int i=1;i<=n;i++)
    
41.         {
    
42.                 cin>>a[i];
    
43.                 b[i]=1;
    
44.         }
    
45.         dfs(1);
    
46.         cout<<num<<endl;
    
47.         return 0;
    
48. }

复制代码

admin

何宇峰你的bool sushu(int x)有重大隐患，x=1不能判断

universehyf

1. 刚才发错了[code]#include<iostream>
   
2. #include<cmath>
   
3. using namespace std;
   
4. int n,k,ii,s;
   
5. long long c;
   
6. int a[25]={};
   
7. bool b[25];
   
8. bool sushu(int x)
   
9. {
   
10.         int y=sqrt(x);
    
11.         for(int z=2;z<=y;z++)
    
12.                 if(x%z==0)
    
13.                         return false;
    
14.         return true;
    
15. }
    
16. void mysearch(int i)
    
17. {
    
18.     int j;
    
19.     if (i==k) {if(sushu(s))c++;}
    
20.     else
    
21.         for (j=0; j<=n-1; j++)
    
22.         {
    
23.             if (b[j])
    
24.             {
    
25.                 s+=a[j];
    
26.                 b[j]=false;
    
27.                 mysearch(i+1);
    
28.                 b[j]=true;
    
29.                 s-=a[j];
    
30.             }
    
31.         }
    
32. }
    
33. int main()
    
34. {
    
35.     cin>>n>>k;
    
36.     for(ii=0;ii<=n-1;ii++) {cin>>a[ii];b[ii]=true;}
    
37.     mysearch(0);
    
38.     cout<<c;
    
39.     return 0;
    
40. }

复制代码

[/code]

diggersun

1. #include <iostream>
   
2. using namespace std;
   
3. const int mm=22;
   
4. int a[mm],aa[mm];
   
5. int n,k,s,ss;
   
6. int p[10000];
   
7. int bb[10000];
   
8. void getp()
   
9. {
   
10.     int i,j;
    
11.     for ( i=2; i<=9999; i++)
    
12.         for ( j=i; i*j<=9999; j++) bb[i*j]=1;
    
13.     j=1;
    
14.     for (int i=2; i<=9999; i++) if (!bb[i]) p[j++]=i;
    
15.     ///for (i=1;i<=j;i++) cout<<p[i]<<' ';
    
16. }
    
17. bool isprime(int x)
    
18. {
    
19.     int i=1;
    
20.     bool b=1;
    
21.     if (x<=1) b=0;
    
22.     else while (p[i]*p[i]<=x && b)
    
23.             if (x%p[i]==0) b=0;
    
24.             else i++;
    
25.     return b;
    
26. 
    
27. }
    
28. void cmn(int i)
    
29. {
    
30.     int j,t;
    
31.     if (i>k)
    
32.     {
    
33.         for (s=0,j=1; j<=k; j++)  s+=aa[a[j]];
    
34.         if (isprime(s)) ss++;
    
35.     }
    
36.     else for (t=a[i-1]+1; t<=n; t++)
    
37.         {
    
38.             a[i]=t;
    
39.             cmn(i+1);
    
40.         }
    
41. }
    
42. int main()
    
43. {
    
44.     getp();
    
45.     cin>>n>>k;
    
46.     for (int i=1; i<=n; i++) cin>>aa[i];
    
47.     cmn(1);
    
48.     cout<<ss;
    
49.     return 0;
    
50. }
    

复制代码

Scorpio

1. #include<iostream>
   
2. #include<cmath>
   
3. using namespace std;
   
4. long long a[24],ia[24];
   
5. long long i,n,k,p;
   
6. void hhh(int i)
   
7. {
   
8.     int j,kk,b=0,s=0;
   
9.     if(i>=k+1)
   
10.     {
    
11.         for(j=1;j<=i;j++)
    
12.             s=s+a[ia[j]];
    
13.         for(j=2;j<=sqrt(s);j++)
    
14.             if(s%j==0)
    
15.                 b=1;
    
16.         if(b==0)
    
17.             p++;
    
18.         s=0;
    
19.     }
    
20.     else for(kk=ia[i-1]+1;kk<=n;kk++)
    
21.     {
    
22.         ia[i]=kk;
    
23.         hhh(i+1);
    
24.     }
    
25. }
    
26. int main()
    
27. {
    
28.     cin>>n>>k;
    
29.     for(i=1;i<=n;i++)
    
30.         cin>>a[i];
    
31.     hhh(1);
    
32.     cout<<p;
    
33.     return 0;
    
34. }
    

复制代码

liubo

1. #include<iostream>
   
2. using namespace std;
   
3. int num[25],pick[25],n,k,ans;
   
4. bool vis[25];
   
5. bool is_prime(int x){
   
6.     int i;
   
7.     for(i = 2;i * i <= x;i++)
   
8.         if(x % i == 0) return 0;
   
9.     return 1;
   
10. }
    
11. void dfs(int tar){
    
12.     if(tar > k){
    
13.         int sum = 0;
    
14.         for(int i = 1;i <= k;i++)
    
15.             sum += num[pick[i]];
    
16.         //cout << sum << " ";
    
17.         if(is_prime(sum)) ans++;
    
18.     }
    
19.     else{
    
20.         for(int i = pick[tar - 1];i <= n;i++){
    
21.             if(!vis[i]){
    
22.                 vis[i] = 1;
    
23.                 pick[tar] = i;
    
24.                 dfs(tar + 1);
    
25.                 vis[i] = 0;
    
26.             }
    
27.         }
    
28.     }
    
29. }
    
30. int main(){
    
31.     cin >> n >> k;
    
32.     for(int i = 1;i <= n;i++)
    
33.         cin >> num[i];
    
34.     pick[0] = 1;
    
35.     dfs(1);
    
36.     cout << ans;
    
37.     return 0;
    
38. }

复制代码

张笑宇

1. #include<iostream>
   
2. #include<cmath>
   
3. using namespace std;
   
4. const int mx=21;
   
5. int a[mx],aa[mx];
   
6. int sum,n,k,s;
   
7. int isprime(int x)
   
8. {
   
9.     int i=2;
   
10.     bool b=true;
    
11.     if (x==0 || x==1) return 0;
    
12.     else
    
13.     {
    
14.         while (i<=sqrt(x) && b)
    
15.         {
    
16.             if (x%i==0) b=false;
    
17.             i++;
    
18.         }
    
19.     }
    
20.     return b;
    
21. }
    
22. void dfs(int i,int sum)
    
23. {
    
24.     int j,kk;
    
25.     if (i>=k+1)
    
26.     {
    
27.         if (isprime(sum)) s++;
    
28.     }
    
29.     else
    
30.     {
    
31.         for (kk=a[i-1]+1; kk<=n; kk++)
    
32.         {
    
33.             a[i]=kk;
    
34.             dfs(i+1,sum+aa[kk]);
    
35.         }
    
36.     }
    
37. }
    
38. int main()
    
39. {
    
40.     cin>>n>>k;
    
41.     for (int i=1; i<=n; i++) cin>>aa[i];
    
42.     dfs(1,0);
    
43.     cout<<s;
    
44.     return 0;
    
45. }
    
46. 
    

复制代码

冯文韬

1. #include<iostream>
   
2. #include<cmath>
   
3. using namespace std;
   
4. int a[25];
   
5. int n,k,ans;
   
6. bool zs(int x){
   
7.         if (x<2) return false;
   
8.         for (int i=2;i<=sqrt(x);i++)
   
9.             if(x%i==0) return false;
   
10.         return true;
    
11. }
    
12. 
    
13. void search(int total,int i,int m){
    
14.         if (m==k&&zs(total)) ans++;
    
15.         if (m<k&&k-m<n-i+1) {
    
16.                 search(total+a[i],i+1,m+1);
    
17.                 search(total,i+1,m);
    
18.         }
    
19.         if (m<k&&k-m>=n-i+1) search(total+a[i],i+1,m+1);
    
20. }
    
21. 
    
22. int main(){
    
23.         cin>>n>>k;
    
24.         for (int i=1;i<=n;i++) cin>>a[i];
    
25.         search(0,1,0);
    
26.         cout<<ans<<endl;
    
27.         return 0;
    
28. }

复制代码

lyc

1. #include<iostream>
   
2. #include<algorithm>
   
3. #include<cmath>
   
4. const int maxn = 25;
   
5. using namespace std;
   
6. bool isprime(int x)
   
7. {
   
8.     for(int i=2; i<=sqrt(x); i++)
   
9.         if(x%i == 0) return false;
   
10.     return true;
    
11. }
    
12. int a[maxn];
    
13. int n,k;
    
14. int ans;
    
15. void dfs(int cnt, int sum, int now)
    
16. {
    
17.     if(cnt == k || now == n+1)
    
18.     {
    
19.         if(isprime(sum) && cnt == k)
    
20.             ans++;
    
21.         return;
    
22.     }
    
23.     dfs(cnt+1, sum+a[now], now+1);
    
24.     dfs(cnt, sum, now+1);
    
25. }
    
26. int main()
    
27. {
    
28.     cin>>n>>k;
    
29.     for(int i=1; i<=n; i++)
    
30.     {
    
31.         cin>>a[i];
    
32.     }
    
33.     dfs(0, 0, 1);
    
34.     cout<<ans;
    
35.     return 0;
    
36. }
    

复制代码