CF251C Number Transformation

小 Petya 非常喜欢正整数。最近他的妈妈送给了他一个正整数 $a$。但有一件事比数字更让 Petya 喜欢：那就是和小 Masha 玩。结果 Masha 已经有了一个正整数 $b$。Petya 决定通过连续执行以下两种操作之一，将他的数字 $a$ 变成数字 $b$: 1. 从他的数字中减去 1。 2. 任选一个整数 $x$，其中 $2\leq x \leq k$，然后从他的数字 $a$ 中减去 $a \bmod x$。操作 $a \bmod x$ 指的是 $a$ 除以 $x$ 的余数。 Petya 每秒可以执行一次操作。每次他可以自由选择当前要执行的哪种操作，并且可以连续执行任意多次同一种操作。 现在，他想知道将数字 $a$ 变为 $b$ 至少需要多少秒。请注意，操作二中每次选择的 $x$ 可以不同且互不相关。

仅有一行，包含三个整数 $a$、$b$（$1\leq b\leq a\leq 10^{18}$）和 $k$（$2\leq k\leq 15$）。 请不要在 C++ 中使用 %lld 格式读取或输出 64 位整数。建议使用 cin、cout 流或 %I64d 格式。

输出一个整数，表示将数字 $a$ 变为数字 $b$ 所需的最少秒数。

在第一个样例中，Petya 转化数字的序列如下：10 $→$ 8 $→$ 6 $→$ 4 $→$ 3 $→$ 2 $→$ 1。 在第二个样例中，其中一种可能的序列为：6 $→$ 4 $→$ 3。 由 ChatGPT 5 翻译