P1036 选数

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. }
    

复制代码

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. }
    

复制代码

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]

admin

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

朱品屹

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. }

复制代码

弑魔者魔眼

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. }

复制代码