Masala #PLI51L2QUF

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 14dan 12ni 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.
Sizga n va m sonlari beriladi siz tepadagi formulalar yordamida javobni chop eting.

Sizga n va m sonlari kiritiladi(2≥n,m≤10**18).

Masalani javobini chop eting.