[开发测试]Codeforces Round #698 (Div. 2) B. Nezzar and Lucky Number

原题链接

题目大意： 给出一个数d和n个数a，问a能不能用若干个含d的十进制数表示出a

输入格式： 第一行包含单个整数t(1≤t≤9)-测试用例的数量。

每个测试用例的第一行包含两个整数q和d(1≤q≤104，1≤d≤9)。

每个测试用例的第二行包含q个整数a1、a2、…。、AQ(1≤ai≤109.)。

输出格式： 对于每个测试用例中的每个整数，如果ai可以等于幸运数字的总和，则在一行中打印“yes”。否则，打印“no”。

您可以使用任何大小写(大写或小写)打印字母。

Example
input
2
3 7
24 25 27
10 7
51 52 53 54 55 56 57 58 59 60
output
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO

先上一个重要结论，对于大于d*10的数a一定表示的出来。
证明：对于大于d * 10的数我们可以将其拆成两部分，一部分是d * 10+C（C是一个常数），另一部分则是a减去第一部分
C等于a的个位数 - d，这样就可以保证第二部分的个位数是d
第二部分的十位D等于a的十位 - d
不够就往前面的位借，（一定是能借到的，因为a大于d * 10）
eg：
假设d=7,a=104
104=77+27
77是第一部分，个位向前面借一位，14-7=7
27是第二部分，十位向前面借一位，9-7=2

对于小于d*10的，我们只需要枚举d的倍数（1-9）如果a - d * x位10的整数倍，则可以表示
否则不能

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=103;
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n,d;
		scanf("%d %d",&n,&d);
		while(n--){
			int x;
			scanf("%d",&x);
			if(x>=d*10){
				printf("YES\n");
				continue;
			}
			else {
				bool flag=0;
				for(int i=1;i<=9;++i){
					if(x<i*d)break;
					else if((x-i*d)%10==0){
						printf("YES\n");
						flag=1;
						break;
					}
				}
				if(!flag)printf("NO\n");
			}
		}
	} 
	return 0;
}