[NOIP2002 普及组] 选数#洛谷

发布时间:2024年01月20日

题目描述

已知 n n n 个整数 x 1 , x 2 , ? ? , x n x_1,x_2,\cdots,x_n x1?,x2?,?,xn?,以及 1 1 1 个整数 k k k k < n k<n k<n)。从 n n n 个整数中任选 k k k 个整数相加,可分别得到一系列的和。例如当 n = 4 n=4 n=4 k = 3 k=3 k=3 4 4 4 个整数分别为 3 , 7 , 12 , 19 3,7,12,19 3,7,12,19 时,可得全部的组合与它们的和为:

3 + 7 + 12 = 22 3+7+12=22 3+7+12=22

3 + 7 + 19 = 29 3+7+19=29 3+7+19=29

7 + 12 + 19 = 38 7+12+19=38 7+12+19=38

3 + 12 + 19 = 34 3+12+19=34 3+12+19=34

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

例如上例,只有一种的和为素数: 3 + 7 + 19 = 29 3+7+19=29 3+7+19=29

输入格式

第一行两个空格隔开的整数 n , k n,k n,k 1 ≤ n ≤ 20 1 \le n \le 20 1n20 k < n k<n k<n)。

第二行 n n n 个整数,分别为 x 1 , x 2 , ? ? , x n x_1,x_2,\cdots,x_n x1?,x2?,?,xn? 1 ≤ x i ≤ 5 × 1 0 6 1 \le x_i \le 5\times 10^6 1xi?5×106)。

输出格式

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

样例 #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,因为这里的范围是左闭右开的。对于组合数的函数运用刷完题单后会进行总结一下

文章来源:https://blog.csdn.net/KLSZM/article/details/135717287
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。