Masala #0426

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 56 %
14

  

Number game

Dasturchilar Klubining a’zosi Azimjon sonlar bilan bo’gliq o’yinlarga juda qiziqadi. Bir kuni Azimjon do’sti Maqsud bilan ajoyib o’yin oynamoqchi bo’ldi. Azimjon o'zi o’ylagan a sonini Maqsud o’ylagan b soniga aylantirish uchun quyidagi amallarni bajarishini aytdi.

  1. Sondan 1 ni olib tashlash.
  2. 2 dan k gacha bo'lgan har qanday butun x sonini tanlab, a sonidan (a mod x) ayirish.
    (a mod x)  operatsiyasi - a sonini x soniga bo'lganda qolgan qildiqni anglatadi.

Azimjon bir soniyada yuqoridagi amallardan birini bajaradi va u o’ylagan a soni ham o’zgarib boraveradi. U o’zining oylagan soni Maqsudning soniga aylanmaguncha, har soniyada o’zi istagan amallardan birini bajaraveradi. Azimjon juda aqilli dasturchi bo’lgani uchun, bu ishni eng kam vaqtda bajaradigan dastur yordamida amalga oshirmoqchi. Siz ham Azimjonga yordam berishga urinib ko’ring

 

E'tibor bering: ikkinchi amaldagi x raqamlari har safar bir-biridan mustaqil ravishda yangidan tanlanadi.


Kiruvchi ma'lumotlar:

Bitta qatorda Azimjon o’ylagan son, Maqsud o’ylagan son va \(k\) soni. \((1 ≤ b ≤ a ≤ 10^{18} ;  2 ≤ k ≤ 15)\).


Chiquvchi ma'lumotlar:

Azimjon eng kamida necha soniya ichida o’z sonini Maqsud o’ylangan songa aylantirishini aniqlang.


Misollar
# input.txt output.txt
1
8 2 3
4
2
15 10 5
2
3
10 1 4
6
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin