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
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
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.
题目大意
Nezzar在 (1，...，9) 中最喜欢的数字是 (d) 。
如果 (d) 在其十进制表示形式中至少出现一次，他将其称为幸运数字。
给定 (q) 个整数 (a_1，a_2，…，a_q) ，对于每个 (1≤i≤q) ，Nezzar想知道 (a_i) 是否可以等于几个（一个或多个）幸运数字的总和。
题解
我们在纸上可以演示一下，如果 (a_i ≥ 100) 则一定可以构造出两个幸运数字其总和一定等于 (a_i)，此处无严格的证明
例1：
(a_i = 123, d = 9)
.---------------------. 如 (a_i) 为3位，则先将十位百位对应补 (d)
○○9
○9○
.---------------------. 在根据当前数将其余的数补齐
○○9
○94
.---------------------. 补齐
○19
○94
.---------------------. 得出答案
123
例2：
(a_i = 1234, d = 5)
.---------------------.
○5○○
○○5○
.---------------------. 在根据当前数将其余的数补齐
0504
0650
.---------------------. 得出答案
1234
综上，我们解决了100及以上的数都输出“YES”
剩下的数因为范围很小，所以我采用暴力方法：
1、若 (a_i) 大于等于 0 向下执行，否则输出no
2、检查 (a_i) 的某一位数字是否等于 (d) （ 若等于则输出yes，否则向下执行）
3、将 (a_i) 自减 (d) 循环执行第 1 步
上段流程即程序代码中的check（）
#include <iostream>
using namespace std;
bool check ( int x, int k )
{
if ( x >= 100 ) return true; // 如果 a_i 大于等于 100 则说明一定存在幸运数字，返回 true
while ( x >= 0 )
{
int t = x; // 保存一下 x 对 t 判断每一位是否等于 d（d的定义为原题目中的d，在这里为 k）
while ( t )
{
int a = t % 10;
if ( a == k ) return true;
t /= 10;
}
x -= k; // 每次将 a_i 自减 d
}
return false;
}
int main ( void )
{
int T;
cin >> T; // 样例个数
while ( T-- )
{
int n, k;
cin >> n >> k; // 询问次数 和 d
for ( int i = 0; i < n; i++ )
{
int a;
cin >> a; // a_i
if ( check( a, k ) ) cout << "YES" << endl; // 如果check返回true，则输出yes，否则输出no
else cout << "NO" << endl;
}
}
return 0;
}
输入输出
