274A.md (1156B)
1 Source: https://codeforces.com/problemset/problem/274/A 2 3 A. k-Multiple Free Set 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 A *k*-multiple free set is a set of integers where there is no pair of integers where one is equal to another integer multiplied by *k*. That is, there are no two integers *x* and *y* (*x* < *y*) from the set, such that *y* = *x*·*k*. 22 23 You're given a set of *n* distinct positive integers. Your task is to find the size of it's largest *k*-multiple free subset. 24 25 Input 26 27 The first line of the input contains two integers *n* and *k* (1 ≤ *n* ≤ 105, 1 ≤ *k* ≤ 109). The next line contains a list of *n* distinct positive integers *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 109). 28 29 All the numbers in the lines are separated by single spaces. 30 31 Output 32 33 On the only line of the output print the size of the largest *k*-multiple free subset of {*a*1, *a*2, ..., *a**n*}. 34 35 Examples 36 37 Input 38 39 ``` 40 6 2 41 2 3 6 5 4 10 42 ``` 43 44 Output 45 46 ``` 47 3 48 ``` 49 50 Note 51 52 In the sample input one of the possible maximum 2-multiple free subsets is {4, 5, 6}.