洛谷P1036选数（素数+组合数）

题目链接：https://www.luogu.org/problemnew/show/P1036 

主要考两个知识点：判断一个数是否为素数、从n个数中选出m个数的组合

判断一个数是否为素数：

素数一定是6n+1或者6n-1

如果是6n，则可以被6整除

如果是6n+2，可以被2整除

如果是6n+3，可以被3整除

如果是6n+4，可以被2整除

而6n+5等同于6n-1

组合数：

参考博客：https://zhidao.baidu.com/question/487981533.html

采用递归，从n个数里选出下标最大的一个数，从n-1个数里再选出下标最大的一个数，直到剩余n-m+1个数，再选出最后一个

如此反复，直到最大的下标为m

代码如下：

#include<cstdio>
#include<cmath>
#define MAXN 500
using namespace std; 

int M;
int cnt;

bool isPrime(int num)
{
    if(num <= 3){
        return num > 1;
    }
    
    if(num % 6 != 1 && num % 6 != 5){
        return false;
    }
    int x = (int)sqrt(num);
    for(int i = 5; i <= x; i += 6){
        if(num % i == 0 || num % (i+2) == 0){
            return false;
        }
    }
    return true;
}

void combine(int a[], int n, int m, int b[]) 
{
    for(int i = n; i >= m; i--){
        b[m-1] = i-1;//b数组存储的是元素下标 
        if(m > 1){
            combine(a, i-1, m-1, b);
        }
        else{
            int sum = 0;
            for(int j = M-1; j >= 0; j--){
                sum += a[b[j]];
            }
            
            if(isPrime(sum)){
                cnt ++;
            }
        }
    }
}



int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    M = m;
    int a[30], b[30];
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    combine(a, n, m, b);
    printf("%d\n", cnt);
    
    return 0;
} 

有任何疑问请站内联系或者邮箱：zhuo2333@qq.com