codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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}.