F. НОД 2.0

В одном из местных НИИ часто требуется находить наибольший общий делитель (НОД) нескольких чисел. Вам уже доверяют, так что вновь пришли с этой задачей.

Формат ввода

В первой строке записано одно число N — количество данных. В каждой из последующих N строк записано по одному натуральному числу.

Формат вывода:

Требуется вывести одно натуральное число — НОД всех данных чисел (кроме N).

Пример

Ввод

2
12
42

Вывод

6

Ввод

3
102
39
768

Вывод

3

Решение

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

Принимаем на вход количество чисел и первое число. Так как НОД одного числа равен самому числу, будем считать это число ответом.
Организуем цикл в котором будем принимать последующие данные. Так как одно число мы уже получили, то цикл должен быть на одну итерацию меньше чем количество данных, полученных на первом шаге.
В цикле выполняем поиск НОД как в задаче F. НОД
По окончанию циклов выводим результат.

Посмотреть код

Решение

Python
count = int(input())

gcd = int(input())

for _ in range(count - 1):
    number = int(input())
    while number != 0 and gcd != 0:
        if number >= gcd:
            number %= gcd
        else:
            gcd %= number
    gcd = gcd + number

print(gcd)

Решение

Python
count = int(input())

gcd = int(input())
# number = 0

for _ in range(count - 1):
    number = int(input())
    while number != 0:
        gcd, number = number, gcd % number

print(gcd)
Подписаться
Уведомить о
guest
0 комментариев
Старые
Новые Популярные
Межтекстовые Отзывы
Посмотреть все комментарии