洛谷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 <= ){

        return num > ;

    }

    if(num %  !=  && num %  != ){

        return false;

    }

    int x = (int)sqrt(num);

    for(int i = ; i <= x; i += ){

        if(num % i ==  || num % (i+) == ){

            return false;

        }

    }

    return true;

}

void combine(int a[], int n, int m, int b[])

{

    for(int i = n; i >= m; i--){

        b[m-] = i-;//b数组存储的是元素下标

        if(m > ){

            combine(a, i-, m-, b);

        }

        else{

            int sum = ;

            for(int j = M-; j >= ; j--){

                sum += a[b[j]];

            }

            if(isPrime(sum)){

                cnt ++;

            }

        }

    }

}

int main()

{

    int n, m;

    scanf("%d%d", &n, &m);

    M = m;

    int a[], b[];

    for(int i = ; i < n; i++){

        scanf("%d", &a[i]);

    }

    combine(a, n, m, b);

    printf("%d\n", cnt);

    return ;

} 

有任何疑问请站内联系或者邮箱：[e-mail]