Еkub va ekukni topish. Evklid algoritmi

Evklid algoritmi
Time limit : 1000 ms
Memory limit : 128 mb
Evklid algoritmi - ikki sonni eng katta umumiy bo'luvchisini(EKUB) topib beruvchi effektiv algoritm hisoblanadi. Algoritm yunon matematiki Evklid nomiga berilgan. U bu algoritmni eramizidan 3 asr oldin o'ylab topgan. Evklid algoritmi ikkita musbat son uchun yangi juftlikni hosil qiladi, kattasini kichginasi orqali kamaytirib. Bu jarayon ikkala son teng bo'lib qolmaguncha davom ettiriladi.
Misol tariqasinda (12,14) juftligini olaylik. Dastlab 12 ni 14 olib tashlaymiz. Hosil bo'lgan juftlik - (12,2). Keyin shu jarayon taqrorlanadi:
EKUB(12,2)=EKUB(10,2)=EKUB(8,2)=EKUB(6,2)=EKUB(4,2)=EKUB(2,2)=2. Shunday qilib javob - 2. Bu algoritmini to'g'riligiga sabab agarda d=EKUB(a,b) bo'lsa demak ikki sonni ayirmasi ham d soniga bo'linadi. Ya'ni (a−b)=0(mod d).
Afsuski, bu algoritm agarda birorta son kichik bo'lib, boshqasi katta bo'lsa juda ko'p amal bajarishiga to'g'ri keladi. Masalan (2,10000001) juftligi uchun 5000000 amal bajariladi EKUBi birligini aniqlash uchun. Ya'ni eng yomon holatda algoritm O(max(a,b)) amal bajarishiga to'g'ri keladi. Buni yanada tez ishlaydigan qilish mumkin. Gap shundaki har safar katta son kichkinasidan max(a,b)/min(a,b) challi ayrilib tashlanadi. Ayirish o'rninga qoldiq olish amalini bajarish mumkin. Shunda har safar katta son kichginadan kichiklashadi. Har safar ikkala sondan bittasi kamida 2 baravar kichraygani uchun ishlash vahti O(log(min(a,b))) tashkil qiladi.
Lekin gap shundaki amalda bu algoritm deyarli O(1) amal bajaradi. Chunki har qanday juftlik uchun bittasi kamida ikki baravarga kichiklashadi dedik, ammo amalda bu kichrayish tezroq va kattaroq suratda bo'ladi. Masalan ushbu (12,14) juftlik uchun EKUBni topish uchun 2 amal kifoya etadi . Lekin shunda ham shunday juftliklar bor-ki ular uchun algoritm ko'p amal bajarishi mumkin. Sizga bu masalada n soni berilgan bo'lib, siz shunday (a,b)1≤atopishingiz kerakki, bu juftliklar uchun Evklid algoritmi eng ko'p amalni bajarsin. Agarda bunday juftliklardan bir nechtasi bo'lsa a si minimalini chiqaring, agarda a si minimalidan bir nechta bo'lsa b si minimal bo'lganni chiqaring. Boshqacha qilib aytgan leksiografik eng kichik javobni chiqaring.