B. Nezzar and Lucky Number
题目
Nezzar’s favorite digit among 1,…,9 is d. He calls a positive integer lucky if d occurs at least once in its decimal representation.
Given q integers a1,a2,…,aq, for each 1≤i≤q Nezzar would like to know if ai can be equal to a sum of several (one or more) lucky numbers.
Input
The first line contains a single integer t (1≤t≤9) — the number of test cases.
The first line of each test case contains two integers q and d (1≤q≤104, 1≤d≤9).
The second line of each test case contains q integers a1,a2,…,aq (1≤ai≤109).
Output
For each integer in each test case, print “YES” in a single line if ai can be equal to a sum of lucky numbers. Otherwise, print “NO”.
You can print letters in any case (upper or lower).
Example
inputCopy
2
3 7
24 25 27
10 7
51 52 53 54 55 56 57 58 59 60
outputCopy
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
Note
In the first test case, 24=17+7, 27 itself is a lucky number, 25 cannot be equal to a sum of lucky numbers.
题意分析
给你一个d,1<=d<=9;任何一个数a中只要有一位是d，则称a,就是幸运数组，现在给你一个数判断他是否可以用一个或者多个幸运数字的和表示。
因为1< t < 9,q <= 10^4,所以每次最多要处理 10^5的数据,所以算法对单个数据的判断应该尽可能的做到原地工作。
思路：
优先考虑YES，当不满足所有YES条件后，就是NO
当用多个幸运数字组成a，则这些数字，各自有一位是d,尝试枚举，后不难发现
①当a >= 10d + 10时，a一定可以被拆分为两个数n1,n2，n1是d,n2十位是d,一定有这样的n1 + n2 = a。11d > a >= 10d十位是d所以也不用判断。所以 a >= d*10时可以原地工作。
②接下来考虑 a < 10d，这样的数要能够拆分为幸运数字，就两种可能，要么自身是幸运数字，只要判断个位是否是d就可以，如果本身不是幸运数字，再考虑是否可以拆分成多个幸运数字。
假设可以拆分，因为a < 10d,所以明显这些拆成的幸运数字不可能10位是d,只能个位是d，a的个位只受组成它的幸运数字的个位（都是d)的影响，因为幸运数字个位为d,所以十位有没有是什么无所谓，只要幸运数字的和小于a就可以，所以就可以在 nd <= num的情况下枚举，看如果nd个位和num个位相同，就说明a，可以拆分为幸运数字。
AC代码
#include <iostream>
using namespace std;int main()
{
int T;int num;int n, d;char c;cin >> T;int flag;for (int t = 0; t < T; t++){
cin >> n >> d;for (int i = 0; i < n; i++){
cin >> num;if (num >= d * 10 || num % 10 == d)//num >=10d {
cout << "YES" << endl;continue;}flag = 0;for (int k = 1; k*d <= num; k++){
if ( k * d % 10 == num % 10){
cout << "YES" << endl;flag = 1;break;}}if (flag)continue;cout << "NO" << endl;}}//system("pause");return 0;
}