B.Nezzar and Lucky Number
生肉{:target=”_blank”}
题目翻译
$\text{Nezzar}$ 最喜欢的数字 $d$ 在 $1, 2, \cdots, 9$ 中。
对于一个正整数,若 $d$ 在这个数中出现了至少一次,则称该数为幸运数。
现在给出 $q$ 个正整数 $a _ 1, a _ 2, \cdots, a _ q$。
对于每个 $1 \leq i \leq q$,$\text{Nezzar}$ 想知道 $a _ i$ 是否可以表示成多个幸运数的和。
输入
第一行包含一个正整数 $t \ (1 \leq t \leq 9)$,表示测试数据组数。
对于每组测试数据:
第一行包含两个整数 $q$ 和 $d \ (1 \leq q \leq 10 ^ 4, 1 \leq d \leq 9)$。
第二行包含 $q$ 个正整数 $a _ 1, a _ 2, \cdots, a _ q$。
输出
对于每组测试数据的每个数 $a _ i$,如果 $a _ i$ 可以表示成多个幸运数的和,则输出 YES
,否则输出 NO
。
样例输入
2
3 7
24 25 27
10 7
51 52 53 54 55 56 57 58 59 60
样例输出
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
算法
(暴力,猜结论) $O(tq)$
定义合法:如果一个正整数数可以被表示成多个幸运数的和,则称 $x$ 是合法的。
结论:对于每个数 $x$,如果 $x \geq 10d$,则 $x$ 合法。
简证一下:
因为 $10d$ 是幸运数,所以如果 $x \text { mod } (10d)$ 合法,则 $x$ 合法。
又因为 $x \geq 10d$,所以如果 $x \text { mod } (10d) + 10d$ 合法,则 $x$ 合法。
那么证明结论,就等价于证明所有满足 $10d \leq x < 20d$ 的 $x$ 都合法。
令 $t = x - 10d$,令 $t = kd + r$,其中 $0 \leq r < d$。
因为 $kd$ 是 $k$ 个 $d$ 相加,而 $d$ 也是幸运数,所以 $kd$ 合法。
所以如果 $x - kd$ 合法,则 $x$ 合法。
$x - kd = x - (t - r) = x - t + r = x - (x - 10d) + r = 10 d + r$
所以如果 $10 d + r$ 合法,那么 $x$ 就合法。
因为 $0 \leq r < d < 10$,所以 $r$ 只有一位。
那么 $10 d + r$ 的十位就是 $d$,所以 $10d + r$ 是幸运数,所以 $10d + r$ 合法。
所以所有满足 $10d \leq x < 20d$ 的 $x$ 都合法。
证毕。
有了这个性质之后,就可以直接判掉所有 $\geq 10d$ 的 $a _ i$。
考虑如何判定剩下的 $< 10d$ 的 $a _ i$。
对于 $< 10d$ 的正整数 $x$,假设 $x$ 合法。
因为 $x$ 合法,可设 $\begin {aligned} x = \sum _ {i = 1} ^ k c _ i \end {aligned}$,其中 $c _ i$ 是幸运数。
又因为 $x < 10d$,所以有 $c _ i < 10d$。
所以 $c _ i$ 必然个位是 $d$。
所以 $x$ 是否是幸运数,就等价于 $x$ 是否可以表示成多个个位是 $d$ 的幸运数之和。
再令 $c _ i = 10b _ i + d$,那么有 $ \begin {aligned} x &\ = \sum _ {i = 1} ^ k 10 b _ i + d = k d + 10 \sum _ {i = 1} ^ k b _ i \end {aligned} $
那么我们可以枚举 $k$,对于每个 $k$,判断 $x - k d$ 是否为 $10$ 的倍数,若是,则 $x$ 合法,否则不合法。
时间复杂度
我们一共要判断 $tq$ 个 $a _ i$。
对于 $a _ i >= 10d$ 的情况,时间复杂度为 $O(1)$。
对于 $a _ i < 10d$ 的情况,我们会枚举 $k$,且 $k d <= x < 10 d$,因此 $k < 10$,时间复杂度为 $O(10) = O(1)$。
所以总时间复杂度为 $O(tq)$。
空间复杂度 $O(1)$。
C++ 代码
#include <cstdio>
#include <cstring>
int task;
int n, x, d;
int main()
{
scanf("%d", &task);
while (task -- )
{
scanf("%d%d", &n, &d);
while (n -- )
{
scanf("%d", &x);
if (x >= d * 10) puts("YES");
else
{
bool yes = false;
for (int k = 1; k * d <= x; k ++ )
if ((x - k * d) % 10 == 0)
{
yes = true;
break;
}
puts(yes ? "YES" : "NO");
}
}
}
return 0;
}
%%%