Masala #PLI51L2QUF

Xotira 32 MB Vaqt 1000 ms Qiyinchiligi 20 %

Muallif: Abduvohid Latibov Saydullo o`gli

Yevklet algoritmi

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.

Kiruvchi ma'lumotlar:

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

Chiquvchi ma'lumotlar:

Masalani javobini chop eting.

Misollar

#	input.txt	output.txt
1	12 14	2

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin