C. Тоо хувиргасан нь

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Бяцхан Петя эерэг бүхэл тоонуудад их дуртай. Саяхан ээж нь түүнд бүхэл тоо $a$-г өгчээ. Петяд тооноос илүү таалагддаг зүйл ганцхан байдаг. Энэ нь бяцхан Машатай тоглох. Харин Машад аль хэдийн бүхэл эерэг тоо $b$ байж гэнэ. Тиймээс Петя өөрийн $a$ тоогоо үйлдлүүд хийж $b$ болгохоор шийджээ. Үйлдлүүд нь дараах хоёр төрөл байх боломжтой:

  1. Өөрийн тооноос $1$-ийг хасах.
  2. $2$-оос $k$-ийн хооронд $x$ бүхэл тоо сонгоно. Тэгээд өөрийн $a$ тооноос $(a\ mod\ x)$ тоог хасна. $(a\ mod\ x)$ гэдэг нь $a$ тоог $x$ тоонд хуваасны дараах үлдэгдлийг хэлнэ.

Петя нэг үйлдлийг нэг секундэд хийнэ. Аль ч үйлдэл байсан одоо хийж байгаа үйлдлээ хийж байхдаа дараагийн үйлдлээ сонгочихсон байдаг. Тэрээр аль ч үйлдлийг хэдэн ч удаа дараалан хийж болно.

Одоо тэрээр хамгийн багадаа хэр хугацаанд өөрийн $a$ тоог $b$ тоонд хувиргаж чадах вэ гэдгийг олохыг хүсч байлаа. Хоёрдугаар төрлийн үйлдлийн $x$ тоог үйлдэл болгон дээр шинээр сонгоно.

Оролт

Нэг мөрөнд $a$, $b$ ($1 ≤ b ≤ a ≤ 10^{18}$), $k$ ($2 ≤ k ≤ 15$) бүхэл тоонууд зайгаар тусгаарлагдан өгөгдөнө.

C++ дээр 64-бит бүхэл тоонуудыг унших эсвэл бичихийн тулд %lld тодорхойлогчийг ашиглахгүй байхыг хүсье. Энд cin, cout streams эсвэл %I64d тодорхойлогчийг ашиглах нь зүйтэй.

Гаралт

$a$ тооноос $b$ тоо болгон өөрчлөхөд шаардагдах хамгийн бага хугацааг хэвлэнэ үү.

Орчуулсан: Энхлут

Жишээ тэстүүд

Оролт
10 1 4
Гаралт
6
Оролт
6 3 10
Гаралт
2
Оролт
1000000000000000000 1 3
Гаралт
666666666666666667

Тэмдэглэл

Эхний жишээнд Петягийн тоо дараах байдлаар өөрчлөгдөнө: $10 → 8 → 6 → 4 → 3 → 2 → 1$.

Хоёр дахь жишээнд боломжит хариунуудын нэг нь: $6 → 4 → 3$.

Сэтгэгдлүүдийг ачааллаж байна...