1312C.md (1900B)
1 Source: https://codeforces.com/problemset/problem/1312/C 2 3 C. Adding Powers 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 standard input 16 17 output 18 19 standard output 20 21 Suppose you are performing the following algorithm. There is an array $v_1, v_2, \dots, v_n$ filled with zeroes at start. The following operation is applied to the array several times — at $i$-th step ($0$-indexed) you can: 22 23 * either choose position $pos$ ($1 \le pos \le n$) and increase $v_{pos}$ by $k^i$; 24 * or not choose any position and skip this step. 25 26 You can choose how the algorithm would behave on each step and when to stop it. The question is: can you make array $v$ equal to the given array $a$ ($v_j = a_j$ for each $j$) after some step? 27 28 Input 29 30 The first line contains one integer $T$ ($1 \le T \le 1000$) — the number of test cases. Next $2T$ lines contain test cases — two lines per test case. 31 32 The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 30$, $2 \le k \le 100$) — the size of arrays $v$ and $a$ and value $k$ used in the algorithm. 33 34 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^{16}$) — the array you'd like to achieve. 35 36 Output 37 38 For each test case print YES (case insensitive) if you can achieve the array $a$ after some step or NO (case insensitive) otherwise. 39 40 Example 41 42 Input 43 44 ``` 45 5 46 4 100 47 0 0 0 0 48 1 2 49 1 50 3 4 51 1 4 1 52 3 2 53 0 1 3 54 3 9 55 0 59049 810 56 ``` 57 58 Output 59 60 ``` 61 YES 62 YES 63 NO 64 NO 65 YES 66 ``` 67 68 Note 69 70 In the first test case, you can stop the algorithm before the $0$-th step, or don't choose any position several times and stop the algorithm. 71 72 In the second test case, you can add $k^0$ to $v_1$ and stop the algorithm. 73 74 In the third test case, you can't make two $1$ in the array $v$. 75 76 In the fifth test case, you can skip $9^0$ and $9^1$, then add $9^2$ and $9^3$ to $v_3$, skip $9^4$ and finally, add $9^5$ to $v_2$.