Adding Powers

Adding Powers

Suppose you are performing the following algorithm. There is an array $v1$v1,$v2$v2,…,$vn$vn filled with zeroes at start. The following operation is applied to the array several times — at $i-th$i−th step ($0$0-indexed) you can:

• either choose position pos $(1≤pos≤n)$(1≤pos≤n) and increase $v_{pos}$vpos​ by $ki$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$v equal to the given array a ($vj=aj$vj=aj for each $j$j) after some step?

Input

The first line contains one integer $T (1≤T≤1000)$T(1≤T≤1000) — the number of test cases. Next $2T$2T lines contain test cases — two lines per test case.

The first line contains one integer $T (1≤T≤1000)$T(1≤T≤1000) — the number of test cases. Next $2T$2T lines contain test cases — two lines per test case.

The second line contains $n$n integers $a1,a2,…,an (0≤ai≤10^{16})$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.

Example
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
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 $k0$k0 to $v1$v1 and stop the algorithm.

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

In the fifth test case, you can skip $9^0$90 and $9^1$91, then add $9^2$92 and $9^3$93 to $v3$v3, skip $9^4$94 and finally, add $9^5$95 to $v2$v2.

思路

题意：给出一个数列，数字k，数列中的每个数字能否由k的n次方加成，且每个次方只能用一次。很明显将每个数字的k进制表示出来，然后判断同一位次上的数字之和是否 $≤1$≤1，这样就可以了，用一个数组统计每一个位次上的和。

代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
const int mx=2e5+10;
int s[100];
ll t,n,k;
ll a[mx];
 
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		bool flag=false;
		memset(s,0,sizeof(s));
		scanf("%lld%lld",&n,&k);
		for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
		for(int i=1;i<=n;i++)
		{
			int j=0;
			while(a[i])//统计每一个数字的k进制
			{
				s[j]+=a[i]%k;//加上同一位次的
				j++;
				a[i]/=k;
			}
	    }
	    for(int i=0;i<100;i++)
	      if(s[i]>1)//只要有超过一次的就不能了
	      {
	      	flag=true;
	      	break;
	      }
	    if(flag)
	    printf("NO\n");
	    else
	    printf("YES\n");
	}
	return 0;
}