B. Divisiblity of Differences

Codeforces

IDCF876B

Time1000ms

Memory512MB

Difficulty—

implementationmathnumber theory

English · Original

Chinese · Translation

Formal · Original

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. ## Input 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. ## Output 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. [samples]

给你一个包含 #cf_span[n] 个整数的多重集。你需要从中恰好选出 #cf_span[k] 个数，使得其中任意两个数的差都能被 #cf_span[m] 整除，或者判断这是不可能的。原始多重集和选出的多重集中可以包含重复的数字，但选出的多重集中任意数字的出现次数不得超过其在原始多重集中的出现次数。第一行包含三个整数 #cf_span[n]、#cf_span[k] 和 #cf_span[m]（#cf_span[2 ≤ k ≤ n ≤ 100 000]，#cf_span[1 ≤ m ≤ 100 000]）——多重集中整数的个数、你需要选出的整数个数，以及所选任意一对整数差值的必需除数。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai ≤ 10^9]）——多重集中的数字。如果无法按要求选出 #cf_span[k] 个数字，则输出 «_No_»（不含引号）。否则，在输出的第一行打印 «_Yes_»（不含引号）。在第二行打印 #cf_span[k] 个整数 #cf_span[b1, b2, ..., bk] —— 选出的数字。如果有多个可能的解，输出任意一个即可。 ## Input 第一行包含三个整数 #cf_span[n]、#cf_span[k] 和 #cf_span[m]（#cf_span[2 ≤ k ≤ n ≤ 100 000]，#cf_span[1 ≤ m ≤ 100 000]）——多重集中整数的个数、你需要选出的整数个数，以及所选任意一对整数差值的必需除数。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai ≤ 10^9]）——多重集中的数字。 ## Output 如果无法按要求选出 #cf_span[k] 个数字，则输出 «_No_»（不含引号）。否则，在输出的第一行打印 «_Yes_»（不含引号）。在第二行打印 #cf_span[k] 个整数 #cf_span[b1, b2, ..., bk] —— 选出的数字。如果有多个可能的解，输出任意一个即可。 [samples]

**Definitions** Let $ n, k, m \in \mathbb{Z}^+ $ with $ 2 \leq k \leq n \leq 100{,}000 $ and $ 1 \leq m \leq 100{,}000 $. Let $ A = (a_1, a_2, \dots, a_n) $ be a multiset of integers with $ 0 \leq a_i \leq 10^9 $. **Constraints** 1. $ 2 \leq k \leq n \leq 100{,}000 $ 2. $ 1 \leq m \leq 100{,}000 $ 3. $ 0 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $ **Objective** Determine if there exists a submultiset $ B \subseteq A $ of size $ k $ such that for all $ x, y \in B $, $ m \mid (x - y) $. If such $ B $ exists, output "Yes" followed by any such $ B $; otherwise, output "No".

Samples

Input #1

3 2 3
1 8 4

Output #1

Yes
1 4

Input #2

3 3 3
1 8 4

Output #2

No

Input #3

4 3 5
2 7 7 7

Output #3

Yes
2 7 7

API Response (JSON)

{
  "problem": {
    "name": "B. Divisiblity of Differences",
    "description": {
      "content": "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 c",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF876B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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.\n\nNumbers c...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给你一个包含 #cf_span[n] 个整数的多重集。你需要从中恰好选出 #cf_span[k] 个数，使得其中任意两个数的差都能被 #cf_span[m] 整除，或者判断这是不可能的。\n\n原始多重集和选出的多重集中可以包含重复的数字，但选出的多重集中任意数字的出现次数不得超过其在原始多重集中的出现次数。\n\n第一行包含三个整数 #cf_span[n]、#cf_span[k] 和 #cf_span[...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k, m \\in \\mathbb{Z}^+ $ with $ 2 \\leq k \\leq n \\leq 100{,}000 $ and $ 1 \\leq m \\leq 100{,}000 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a multiset of integers with $ 0 \\leq...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments