洛谷p1036-选数

题目描述

题解代码

#include<bits/stdc++.h>
using namespace std;
// 4 3
// 3 7 12 19
int n,m;
int ans;
const int N=50;

int  haduse[N];
int  num[N];

bool isprime(int num)  
{   
      for(int i=2;i<=sqrt(num);i++)
               { 
                    if(num%i==0)
                       return false;
                      

               }
                  
      return true; 
}

void dfs(int u,int start)  //start指的是当前最小开始枚举的数字
   {    //递归的结束条件  use等于所选的m的时候
       if(u==m+1) //生成一个全排列对应的下标
            {   int sum=0;
              for(int i=1;i<=m;i++)
                  { //cout<<num[haduse[i]]<<" ";
                     
                      sum+=num[haduse[i]];
                       if(i==m)
                           {  //cout<<sum<<endl;
                               if(isprime(sum)) ans++;
                           }
                      }
                 return;
            }
         
         //从当前start开始枚举
            for(int i=start; i<=n;i++)
                 {    haduse[u]=i;
                      dfs(u+1,i+1);

                      haduse[u]=0;
                 }
       

   }


int main()
   {   cin>>n>>m;
       for(int i=1;i<=n;i++)
            {
                 cin>>num[i];

            }
      
       dfs(1,1);
       
   
    cout<<ans<<endl;

   }