Adding Powers

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:

  • either choose position $$$pos$$$ ($$$1 \le pos \le n$$$) and increase $$$v_{pos}$$$ by $$$k^i$$$;
  • or not choose any position and skip this step.

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?

Input

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.

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.

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.

Output

For each test case print YES (case insensitive) if you can achieve the array $$$a$$$ after some step or NO (case insensitive) otherwise.Exampleinput

5
4 100
0 0 0 0
1 2
1
3 4
1 4 1
3 2
0 1 3
3 9
0 59049 810

output

YES
YES
NO
NO
YES

Note

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.

In the second test case, you can add $$$k^0$$$ to $$$v_1$$$ and stop the algorithm.

In the third test case, you can’t make two $$$1$$$ in the array $$$v$$$.

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

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
 
int _,n,k;
ll a[1010];
bool check() {
    set<int> pos;
    rep(i,0,n) {
        ll x=a[i];
        int d=0;
        while (x) {
            if (x%k!=0&&x%k!=1) {
                return 0;
            }
            if (x%k==1) {
                //printf("dd %d\n",d);
                if (pos.count(d)) return 0;
                pos.insert(d);
            }
            d+=1;
            x/=k;
        }
    }
    return 1;
}
int main() {
    for (scanf("%d",&_);_;_--) {
        scanf("%d%d",&n,&k);
        rep(i,0,n) scanf("%lld",a+i);
        puts(check()?"YES":"NO");
    }
}

Be the first to comment

Leave a Reply

Your email address will not be published.


*