记录编号	331135	评测结果	AAAAA
题目名称	[NOIP 2002]选数	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2016-10-27 13:38:13	内存使用	0.29 MiB

#include <cstdio>
#include <ctime>
#include <cstdlib>
typedef long long LL;
int fast_pow(int base, int exp, int mod)
{
    LL ans = 1;
    LL k = base;
    while(exp)
    {
        if(exp & 1)
        {
            ans *= k;
            ans %= mod;
        }
        exp >>= 1;
        k *= k;
        k %= mod;
    }
    return ans;
}

bool is_prime(int x)
{
    if(x < 2)return false;
    if(x == 2)return true;
    for(int i = 0; i < 20; i++)
    {
        int a = rand()%(x-2)+1;
        if(fast_pow(a, x-1, x) != 1)
            return false;
    }
    return true;
}
int main()
{
    freopen("choose.in", "r", stdin);
    freopen("choose.out", "w", stdout);
    srand(time(NULL));
    int n, k;
    int a[22];
    scanf("%d %d", &n, &k);
    for(int i = 0; i < n; i++)
        scanf("%d", a+i);
    int r = 0;
    for(int i = 0; i < (1<<n); i++)
    {
        int c = 0;
        int s = 0;
        for(int j = 0; j < n; j++)
        {
            if(i & (1<<j))
            {
                c++;
                s += a[j];
            }
        }
        if(c == k && is_prime(s))r++;
    }
    printf("%d\n", r);
    return 0;
}