钾肥喵的窝

我在 CODING 部署的 Hexo 博客

0%

Codeforces Round #698 (Div. 2) B. Nezzar and Lucky Number

题面

B. Nezzar and Lucky Number

暴力打表

根据某位大佬的反馈, 本题完全暴力也是能过的, 但是我就是想打表.
当然, 只需要打一部分的表就可以了, 我们可以证明当ai >= 10 * dai必然可以分解成lucky number的和. 所以我们只需要打到 10 * d 就可以了.

结论证明

我们设ai = 10 * d + k, 那么显然我们只需要考虑k能否分解了, 令k = x * 10 + y.
10 * d <= ai < 11 * d时, 十位上就是d, 显然成立.
ai >= 11 * d时, 我们可以将ai分解成10 * d + yx * 10 + d, 显然成立.

完整AC代码

这里打表打到了11 * b(因为是凭感觉写的, 当时并没有严谨的证明)