Codeforces 1478B Nezzar and Lucky Number

https://codeforces.com/problemset/problem/1478/B

题意：

给定一个数字$d$ (1 $\le$ $d$ $\le$ 9),如果一个数字某一位上有$d$，则这个数字为一个幸运数字，例如当$d=7$ 时 $7,17,27,71,72$ 等都是幸运数字，给定一个$a$，问是否存在一个或多个幸运数字使得它们的和为$a$

结论：

1. 当 $a\ge 10d$ 时，一定可以构造一组解
2. 当 $a<10d$ 时，满足一定条件的数可以构造出一组解

证明:

1.当 $a\ge 10d$ 时, 一定可以构造一组解，具体证明如下：

• 当 $10d\le a\le 20d$ 时，找到一个 $t$ ($t$可以取0) 满足 $a-10d-t\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}d)$, 则可以构造一组解 10 d + t , d , d , ⋯ , d ⏟ a − 10 d − t d 个 {10d + t}, \underbrace{d,d,\cdots,d}_{\frac{a - 10d - t}{d}个} 10d+t,da−10d−t​个 d,d,⋯,d​​。
  例如：当$a=88，d=7$时，可以找到一个$t=4$，那么$74+7+7=88$，显然$74,7,7$为一组解
• 当 $a>20d$ 时，我们可以先让 $a$ 减去若干个 $10d$ 使得减完后的 $a$ 满足 $10d\le a\le 20d$ , 那此时就可以构造出一组解。

2. 当 $a<10d$ 时，满足一定条件的数可以构造出一组解， 具体证明如下：

• 设 $x$ 为 $a$ 的个位数，如果能找到一个最小的 $n$ 使得 $nd\equiv x(\mathrm{m}\mathrm{o}\mathrm{d}10)$，并且 $nd\le a$，则可以构造一组解 d , d , ⋯ , d ⏟ n − 1 个 , a − ( n − 1 ) d \underbrace{d,d,\cdots,d}_{{n - 1}个},{a - (n - 1)d} n−1个 d,d,⋯,d​​,a−(n−1)d
  当我们能够找到一个最小的$n$满足 $nd\equiv x(\mathrm{m}\mathrm{o}\mathrm{d}10)且nd\le a$时，说明$nd和a$的个位数相同，那么让$a-nd$ 则可以得到一个能被$10$整除的数$c$
  例如：当$a=51,d=7$时, 我们可以找到一个$n=3$满足上述式子，此时有$a-nd=c$,也就是$51-21=30$,此时$c$的个位数为$0$,那么$c+d$就一定是一个幸运数字，我们让等号两边都加上一个$d$则有$a-(n-1)d=c+d$ 也就是 $51-14=37$, 可以把$14$拆成 $7+7$，则此时有一组解为$7,7,37$

代码

#include 
using namespace std;bool check(int x, int d){for(int i = 1; i * d <= x; i++)if(i * d % 10 == x % 10) return true;return false;
}int main(){int t;scanf("%d", &t);while(t--){int n, d, x;scanf("%d%d", &n, &d);for(int i = 1; i <= n; i++){scanf("%d", &x);if(x >= d * 10 || check(x, d)) puts("YES");else puts("NO");}}return 0;
}

参考博客：https://blog.csdn.net/weixin_42856843/article/details/113373162

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！