Codeforce 1312C - Adding Powers （模拟，思维）

Codeforce 1312C Adding Powers

题目：
Suppose you are performing the following algorithm. There is an array v1,v2,…,vn 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≤pos≤n) and increase vpos by ki ;
• 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 (vj=aj for each j) after some step?

---

Input

The first line contains one integer T (1≤T≤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≤n≤30, 2≤k≤100) — the size of arrays v and a and value k

used in the algorithm.

The second line contains n
integers a1,a2,…,an (0≤ai≤1016) — 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.

---

Sample Input

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

Sample Output

YES
YES
NO
NO
YES

题目大意：
告诉你一个数组里有多少个数n,告诉你一个基数k，问你数组里的数，能不能表示为k的幂的形式的和，而且k的幂不能重复

题目分析：
我开始想的 一个数如果可以表示为k的幂的和，那么它可以整除k，或者除以k余1.
所以我用mark来标记，这个数是否满足mod k 等于0或1，同时还要满足，k的幂不能重复使用，所以我用num数组来记录 幂使用的次数（2 的64次幂已经20位数了，所以num数组开64就够了），但是，我得到了一发 RE 。。。。

RE代码：

#include<stdio.h>
#include<cmath>
#include<iostream>
#include<string.h>
// 2的64次方好像20位数 
long long int a,num[64];
int main(){
    int t,n,k;
    scanf("%d",&t);
    while(t--){
    	int mark=1;
    	memset(num,0,sizeof(num));
    	scanf("%d%d",&n,&k);
    	for(int i=0;i<n;i++){
    		scanf("%lld",&a);
    		if(a%k==0||a%k==1){
    		 	while (a>0){
    		 	int s;
    		 	long long j=1;
    		 	for( s=1;j<=a;s++){
    		 		j*=k;
    			}
    			num[s-1]++;
    			a=a-j/k;//把a逐渐分解成k的次幂
    			}//while 在这里结束
    		}
    		else {
    			mark=0;
    			break;
    		}
    	}
    	if(mark==1){
    		for(int i=0;i<64;i++){
    			if(num[i]>1){
    				mark=0;
    				break;
    			}
    		}
    		if(mark==1)
    		printf("YES\n");
    		else 
    		printf("NO\n");
    	}
    	else{
    		printf("NO\n");
    	}
    }
}

codeforces 给出了 除0 的错误。。。但是，我并没有输入0 吖。。。


这是错误的那组数据

1000
6 3
392 471 378 1066 958 1518
6 3
243 0 36 0 1 2190
6 3
90 27 729 2187 4 0
6 3
0 27 1 0 252 729
6 3
132 2167 726 710 1367 334
6 3
1794 146 950 1466 1095 369
6 3
0 324 1 2196 759 0
6 3
1187 677 1728 2101 2033 747
6 3
471 1485 870 1567 335 867
6 3
2514 10 0 0 27 0
6 3
1806 69 890 359 1128 1623
6 3
951 1740 2128 242 190 40
6 3
2187 732 9 324 27 0
6 3
0 1 81 243 2187 27
6 3
1338 242 1333 1703 694 1072
6 3
82 0 243 0 36 3
6 3
733 2430 81 0 0 9
6 3
1015 395 1452 1320 10 1...

---

经过思考，我去掉了mark 的判断，因为即使 mod k 不等于0 或1， 多余的都是靠 k的0次幂堆上去的，所以还是可以判断。结果就AC了，至于 除0 的错误还是没有解决，

AC代码：

#include<stdio.h>
#include<cmath>
#include<iostream>
#include<string.h>
// 2的64次方好像20位数 
long long int a,num[64];
long long int t,n,k;
long long j=1;
int main(){
	scanf("%lld",&t);
	while(t--){
		memset(num,0,sizeof(num));
		scanf("%lld%lld",&n,&k);
		for(int  i=0;i<n;i++){
		 	scanf("%lld",&a);	
		 	while (a>0){
		 		long long  s;
				j=1;
				for( s=1;j<=a;s++)
				{
					j*=k;
				}
				num[s-1]++;
				j/=k;
				a=a-j;
			}//while 在这里结束 
		}
		long long  h;
		for(h=0;h<64;h++){
			if(num[h]>1){
				break;
			}
		}
		if(h!=64)
		printf("NO\n");
		else 
		printf("YES\n");
	
	}
}

不知有没有哪位路过的大佬可以看看我的错误，解答一下，