codeforces-scrape

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

1641A.md (2064B)


      1 Source: https://codeforces.com/problemset/problem/1641/A
      2 
      3 A. Great Sequence
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 A sequence of positive integers is called great for a positive integer $x$, if we can split it into pairs in such a way that in each pair the first number multiplied by $x$ is equal to the second number. More formally, a sequence $a$ of size $n$ is great for a positive integer $x$, if $n$ is even and there exists a permutation $p$ of size $n$, such that for each $i$ ($1 \le i \le \frac{n}{2}$) $a_{p_{2i-1}} \cdot x = a_{p_{2i}}$.
     22 
     23 Sam has a sequence $a$ and a positive integer $x$. Help him to make the sequence great: find the minimum possible number of positive integers that should be added to the sequence $a$ to make it great for the number $x$.
     24 
     25 Input
     26 
     27 Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 20\,000$) — the number of test cases. Description of the test cases follows.
     28 
     29 The first line of each test case contains two integers $n$, $x$ ($1 \le n \le 2 \cdot 10^5$, $2 \le x \le 10^6$).
     30 
     31 The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$).
     32 
     33 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     34 
     35 Output
     36 
     37 For each test case print a single integer — the minimum number of integers that can be added to the end of $a$ to make it a great sequence for the number $x$.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 4
     45 
     46 4 4
     47 
     48 1 16 4 4
     49 
     50 6 2
     51 
     52 1 2 2 2 4 7
     53 
     54 5 3
     55 
     56 5 2 3 5 15
     57 
     58 9 10
     59 
     60 10 10 10 20 1 100 200 2000 3
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 0
     67 2
     68 3
     69 3
     70 ```
     71 
     72 Note
     73 
     74 In the first test case, Sam got lucky and the sequence is already great for the number $4$ because you can divide it into such pairs: $(1, 4)$, $(4, 16)$. Thus we can add $0$ numbers.
     75 
     76 In the second test case, you can add numbers $1$ and $14$ to the sequence, then you can divide all $8$ integers into such pairs: $(1, 2)$, $(1, 2)$, $(2, 4)$, $(7, 14)$. It is impossible to add less than $2$ integers to fix the sequence.