CF876B.Divisiblity of Differences
普及-
通过率:0%
时间限制:1.00s
内存限制:512MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given a multiset of n integers. You should select exactly k of them in a such way that the difference between any two of them is divisible by m, or tell that it is impossible.
Numbers can be repeated in the original multiset and in the multiset of selected numbers, but number of occurrences of any number in multiset of selected numbers should not exceed the number of its occurrences in the original multiset.
给你一个包含 n 个整数的多重集。你需要从中恰好选出 k 个数,使得其中任意两个数之差都能被 m 整除;若无法做到,则需说明这是不可能的。
原始多重集中可能存在重复的数,选出的多重集中也可能包含重复的数,但选出的多重集中任一数字的出现次数不得超过其在原始多重集中的出现次数。
输入格式
First line contains three integers n, k and m (2 ≤ k ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000) — number of integers in the multiset, number of integers you should select and the required divisor of any pair of selected integers.
Second line contains n integers _a_1, _a_2, ..., a__n (0 ≤ a__i ≤ 109) — the numbers in the multiset.
第一行包含三个整数 n、k 和 m(满足 2 ≤ k ≤ n ≤ 100000,1 ≤ m ≤ 100000)—— 分别表示多重集中的整数个数、需选出的整数个数,以及所选任意两个整数必须具有的公因数 m。
第二行包含 n 个整数 a1,a2,...,an(满足 0 ≤ ai ≤ 109)—— 多重集中的各个数字。
输出格式
If it is not possible to select k numbers in the desired way, output «No» (without the quotes).
Otherwise, in the first line of output print «Yes» (without the quotes). In the second line print k integers _b_1, _b_2, ..., b__k — the selected numbers. If there are multiple possible solutions, print any of them.
如果无法按要求选出 k 个数,则输出 No(不带引号)。
否则,在输出的第一行打印 Yes(不带引号);在第二行打印 k 个整数 b1, b2, …, bk —— 即所选出的数。若存在多种可能的解,输出任意一种即可。
输入输出样例
输入#1
3 2 3 1 8 4
输出#1
Yes 1 4
输入#2
3 3 3 1 8 4
输出#2
No
输入#3
4 3 5 2 7 7 7
输出#3
Yes 2 7 7
输入解题思路,AI测评打分。不知道怎么写?