题意

每次不能重复使用k的幂,问能不能构造数组中的每一个数。

思路

810 = 9 * 9 + 9 * 9 * 9这个例子举例

特判1
然后考虑其它:如果a[i]能整除k 每次除去k,t+1
直到不能整除k,此时之前整除过k那么可以尝试去-1,要是-1之后能整除k了说明遇到了加数的一项(并记录t),继续整除直到a[i]也等于1说明找到了最后一项加数
如果之前没有整除过k,比如5,此时如果k^0=1没有用过,就去减1,否则就不合法

另一个方法：重大到小一次贪心减k^幂次，遇到重复就不合法。没想到这个贪心

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+10;
int n,k;
ll a[200],vis[maxn];
set<ll> se;
//题意：每次不能重复使用幂,问能不能构造数组中的每一个数。 

//特判1 
//其它:如果能整除k 每次除去k,t+1
//直到不能整除k,此时之前整除过k那么可以尝试去-1,要是-1之后能整除k了说明遇到了加数的一项(并记录t),继续整除直到a[i]也等于1说明找到了最后一项加数 
//如果之前没有整除过k,比如5,此时如果k^0=1没有用过,就去减1,否则就不合法 
int main(){
    int t;
    cin>>t;
    while(t--){
        se.clear();
        cin>>n>>k;
        for(int i=0;i<=n+100;i++) vis[i] = 0;
        bool flag = true;
        for(int i=1;i<=n;i++) {
            cin>>a[i];
            if(a[i] != 0 && se.find(a[i]) != se.end()){
                flag = false; //重0以外 其他数不能重复 
            }
            se.insert(a[i]);
        }
        if(flag == false){
            puts("NO");
            continue;
        }
        for(int i=1;i<=n;i++){
            if(a[i] == 0) continue;
            int t = 0;
            bool flag2 = false;
            while(1){
                if(a[i] == 1){ //特判1 
                    if(vis[0] == 0){
                        vis[0] = 1;
                    }else{
                        flag = false;
                        break;
                    }
                }else{
                    while(a[i] != 1){  
                        if(a[i] % k == 0){ //能整除 就+1 flag2表示这轮整除过 
                            a[i] = a[i]/k;
                            flag2 = true;
                            t++;
                        }else{
                            if(flag2 == true){
                                if(vis[t] == 0){ //查重有没有使用过t 
                                    a[i] = a[i]-1;
                                    vis[t] = 1;
                                }else{
                                    flag = false; 
                                    break;
                                }
                            }
                            else if(vis[0] == 0){ //比如5这个数 会进入这个if中 那么我们判断之前有没有用过k^0 = 1 
                                a[i] = a[i]-1;
                                vis[0] = 1;
                            }
                            if(a[i]!=0 && a[i]%k!=0){
                                flag = false;
                                break;
                            }
                        }
                    }
                    if(vis[t] == 0){
                        vis[t] = 1;
                    }else{
                        flag = false;
                        break;
                    }
                }
                if(flag == false) break;
                if(a[i] == 1) break;
            }
        }
        if(flag) puts("YES");
        else puts("NO");
    }
    return 0;
} 
/*
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


1
5 4
0 3 4 4 8

1
1 9
10

1
3 9
0 59049 810

1
5 2
1 2 4 8 17
0 1 2 3 4+1

1
5 2
8 0 2 4 80
80/2 = 40
40/2 = 20
20/2 = 10
10/2 = 5

1
5 2
8 4 32 66 17
3 2 5  6-1 4-0

1000
5 2
20 0 33 2 64
5 2
8 0 2 4 80
5 2
8 63 13 42 5
5 2
22 48 7 11 59
5 2
8 4 32 66 17
5 2
70 1 0 16 8
*/