B. Nezzar and Lucky Number_ezzar's favorite digit among 1,\ldots,91,…,9 is dd

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44