[NOIP2002 普及组] 选数#洛谷-Toy模板网

这篇具有很好参考价值的文章主要介绍了[NOIP2002 普及组] 选数#洛谷。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述

已知 $n$ 个整数 $x_1,x_2,\cdots,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$ （ $\le n \le 20$ ， $k < n$ ）。

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

输出格式

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

样例 #1

样例输入 #1

4 3
3 7 12 19

样例输出 #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，因为这里的范围是左闭右开的。对于组合数的函数运用刷完题单后会进行总结一下文章来源地址https://www.toymoban.com/news/detail-809089.html

到了这里，关于[NOIP2002 普及组] 选数#洛谷的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！