AT_arc052_d.[ARC052D] 9

整数 $9$ 有一个有趣的性质。无论选择哪个非负整数 $N$，$N$ 除以 $9$ 的余数与 $N$ 的十进制表示各位数字之和除以 $9$ 的余数总是相同的。

高桥君对是否还有其他具有这种性质的整数感到好奇。然而，遗憾的是，除了 $9$、$3$ 和 $1$ 之外，几乎找不到其他具有这种性质的整数。因此，他决定将条件放宽，从“无论选择哪个非负整数 $N$”变为“对于尽可能多的非负整数 $N$”来进行探索。

高桥君想知道，对于一个非负整数 $K$，有多少个非负整数 $N$ 满足上述性质。

请帮助高桥君回答以下问题：

• 在 $1 \leq N \leq M$ 的整数 $N$ 中，满足 $N$ 除以 $K$ 的余数与 $N$ 的十进制表示各位数字之和除以 $K$ 的余数相等的 $N$ 的个数是多少？

输入以以下格式从标准输入给出。

$K$ $M$

请输出满足题目条件的非负整数的个数，输出一行。

限制条件

• 给定的数字均为整数。
• $1 \leq K \leq M \leq 10^{10}$

部分分

本题设置了部分分。

• 对于满足 $1 \leq M \leq 10^5$ 的数据集，答对可得 $10$ 分。
• 对于满足 $1 \leq M \leq 10^{10}$ 的数据集，答对可再得 $90$ 分，总分为 $100$ 分。

样例解释 1

所有一位数的整数必然满足条件。除此之外，满足 $50 \leq N \leq 59$ 的整数也都满足条件。在 $100$ 以下的范围内，没有其他满足条件的整数。因此，输出 $19$。

由 ChatGPT 4.1 翻译