Арифметика

Практическая часть программирования на языке Python.

Программирование на Python: Задачи

Задача №4179. Алгоритм Евклида

Даны два натуральных числа. Вычислите их наибольший общий делитель при помощи алгоритма Евклида, реализованного без использования рекурсии.

Входные данные
Вводится два натуральных числа.

Выходные данные
Выведите ответ на задачу.

Примеры

Ввод Вывод
1
1
1

Решение
import math
a = int(input())
b = int(input())
print(math.gcd(a, b))

Задача №4180. Бинарный алгоритм Евклида

В бинарном алгоритме Евклида не используются операции деления и остатка, а используется только проверка на чётность и деление на 2. Идея бинарного алгоритма Евклида следующая: НОД(a, b) = 2НОД(a/2, b/2), если a и b четные,
НОД(a, b) = НОД(a/2, b), если a четное, b нечетное,
НОД(a, b) = НОД(a, b/2), если a нечетное, b четное,
НОД(a, b) = НОД(a - b, b), если a и b нечетные, a≥b.

Реализуйте бинарный алгоритм Евклида для вычисления НОД двух чисел.

Входные данные
Вводятся два натуральных числа.

Выходные данные
Выведите ответ на задачу.

Примеры

Ввод Вывод
1
1
1

Ввод Вывод
2
1
1

Ввод Вывод
2
2
2

Решение
a, b = int(input()), int(input())

def binary(a, b):
     move = 0
     if a == 0:
          return b
     if b == 0:
          return a
     while (a | b) & 1 == 0:
          move += 1
          a >>= 1
          b >>= 1
     while a & 1 == 0:
          a >>= 1
     while b != 0:
          while b & 1 == 0:
               b >>= 1
          if a > b:
               a, b = b, a
          b -= a
     return a << move

print(binary(a, b))