[NOIP2002 普及组] 选数#洛谷

题目描述

已知 $n$ 个整数 $x_1,x_2,?,x_n$，以及 $1$ 个整数 $k$（$k<n$）。从 $n$ 个整数中任选 $k$ 个整数相加，可分别得到一系列的和。例如当 $n=4$，$k=3$，$4$ 个整数分别为 $3,7,12,19$ 时，可得全部的组合与它们的和为：

$3+7+12=22$

$3+7+19=29$

$7+12+19=38$

$3+12+19=34$

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：$3+7+19=29$。

输入格式

第一行两个空格隔开的整数 $n,k$（$1\le n\le 20$，$k<n$）。

第二行 $n$ 个整数，分别为 $x_1,x_2,?,x_n$（$1\le x_i\le 5\times 10^6$）。

输出格式

输出一个整数，表示种类数。

样例 #1

样例输入 #1

4 3
3 7 12 19

样例输出 #1

1

提示

【题目来源】

NOIP 2002 普及组第二题

from itertools import combinations
import math


def judge(num):
    if num<=1:
        return False
    for i in range(2,int(math.sqrt(num))+1):
        if num%i==0:
            return False
    return True


if __name__=="__main__":
    n, m = map(int, input().split())
    mapp = list(map(int, input().split()))
    value_ans = 0
    for item in combinations(mapp, m):
        value_key = 0
        for j in range(len(item)):
            value_key += item[j]
        # print(value_key)
        if judge(value_key):
            # print(value_key)
            value_ans += 1
    print(value_ans)

本题目用到了tertools库中的combinations函数。来自 itertools 模块的函数 combinations(list_name, x) 将一个列表和数字 ‘x’ 作为参数，并返回一个元组列表，每个元组的长度为 ‘x’，其中包含x个元素的所有可能组合。列表中元素不能与自己结合，不包含列表中重复元素。这样可以得到从n个数中选取m个数的所有组合。其按照元组的方式储存。遍历的时候当成列表遍历即可。再就是素数的判断，遍历的时候考虑到开方优化的方案时要记得加1，因为这里的范围是左闭右开的。对于组合数的函数运用刷完题单后会进行总结一下