Алгоритм Евклида

@cool99999 · Регистрация: 13.08.2021

Студворк — интернет-сервис помощи студентам

Андрей недавно начал изучать информатику. Одним из первых алгоритмов, который он изучил, был алгоритм Евклида для нахождения наибольшего общего делителя (НОД) двух чисел. Напомним, что наибольшим общим делителем двух чисел a и b называется наибольшее натуральное число x, такое, что и число a, и число b делится на него без остатка.

Алгоритм Евклида заключается в следующем:

1.Пусть a, b — числа, НОД которых надо найти.

2.Если b = 0, то число a — искомый НОД.

3.Если b > a, то необходимо поменять местами числа a и b.

4. Присвоить числу a значение a – b.

5.Вернуться к шагу 2.

Андрей достаточно быстро освоил алгоритм Евклида и вычислил с его помощью много наибольших общих делителей. Поняв, что надо дальше совершенствоваться, ему пришла идея решить новую задачу. Пусть заданы числа a, b, c и d. Требуется узнать, наступит ли в процессе реализации алгоритма Евклида для заданной пары чисел (a, b) такой момент, когда перед исполнением шага 2 число a будет равно c, а число b будет равно d.

Требуется написать программу, которая решает эту задачу.

Входные данные
Первая строка входных данных содержит количество наборов входных данных K (1 ≤ K ≤ 100). Далее идут описания этих наборов. Каждое описание состоит из двух строк. Первая из них содержит два целых числа: a, b (1 ≤ a, b ≤ 10¹⁸). Вторая строка – два целых числа: c, d (1 ≤ c, d ≤ 10¹⁸).

Все числа в строках разделены пробелом.

Выходные данные
Для каждого набора входных данных выведите слово «YES», если в процессе применения алгоритма Евклида к паре чисел (a, b) в какой-то момент получается пара (c, d). В противном случае выведите слово «NO».

Примеры
входные данные
2
20 10
10 10
10 7
2 4
выходные данные
YES
NO

@Dax · 19.08.2021, 15:46

cool99999, пойдет?

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
def gcd(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    print(a)
 
 
if __name__ == '__main__':
    a = int(input())
    b = int(input())
    gcd(a, b)

@cool99999 · 19.08.2021, 15:52 **[ТС]**

к сожалению нет.

@Catstail · 19.08.2021, 16:30

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def gcd(a,b,c,d):
    if (a==c and b==d):
        return "YES"
    elif b==0:
        return "NO"
    if b>a:
        a,b=b,a
    return gcd(a-b,b,c,d)
        
n=int(input())
res=""
for i in range(n):
    a,b=tuple(map(int,input().split()))
    c,d=tuple(map(int,input().split()))
    res=res+gcd(a,b,c,d)+"\n"
print(res)

@cool99999 · 19.08.2021, 17:00 **[ТС]**

программа прошла 29 тестов из 92. В тех которые не прошла пишет: Ошибка во время выполнения программы

@Catstail · 19.08.2021, 22:28

cool99999, я плАчу... Может, рекурсия не нравится. Попробуй так:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def gcd(a,b,c,d):
    while True:
        if (a==c and b==d):
            return "YES"
        elif b==0:
            return "NO"
        if b>a:
            a,b=b,a
        a=a-b    
 
n=int(input())
res=""
for i in range(n):
    a,b=tuple(map(int,input().split()))
    c,d=tuple(map(int,input().split()))
    res=res+gcd(a,b,c,d)+"\n"
print(res)

@Gdez · 19.08.2021, 22:40

Catstail, в задаче входные данные "тяжелые"...

@Catstail · 19.08.2021, 22:42

Gdez, да, я прохлопал (10¹⁸ - это немало)

@cool99999 · 20.08.2021, 10:59 **[ТС]**

прошло 30 из 92

@eaa · 20.08.2021, 12:01

Python
1
2
3
4
5
6
7
8
9
10
for _ in range(int(input())):
    a, b = map(int, input().split())
    c, d = map(int, input().split())
    while b:
        if b == d and a >= c and (c - a) % b == 0:
            print('YES')
            break
        a, b = b, a % b
    else:
        print('NO')

@cool99999 · 20.08.2021, 12:40 **[ТС]**

82 из 92 правильно. В остальных написано "неправильный ответ"

@Garry Galler · 20.08.2021, 12:48

Сообщение от cool99999

82 из 92 правильно. В остальных написано "неправильный ответ"

Может, ты уже сам начнешь думать?
Тебе дали несколько правильных решений. То, что они не проходят тесты, никого не .. ну ты понял.
Это уже твоя проблема.

@cool99999 · 20.08.2021, 13:25 **[ТС]**

1. может.
2. решения частично правильные. Ну так если программа не проходит все тесты, значит она частично правильная.
3. так проблема изначально была моя. Я попросил помощи у профи. Что здесь плохого?

@eaa · 20.08.2021, 13:27

В 5й строке нужно ещё одно условие добавить

@cool99999 · 20.08.2021, 13:37 **[ТС]**

какое?

@Garry Galler · 20.08.2021, 13:38

Не по теме:

Сообщение от cool99999

Я попросил помощи у профи.

Этот раздел не для помощи, а для лентяев, которые самостоятельно ничего не могут и хотят готового решения.
Хочешь помощи - иди в другой раздел и предоставляй свой вариант решения.

@cool99999 · 20.08.2021, 14:00 **[ТС]**

1. для помощи или для лентяев, которые самостоятельно ничего не могут и хотят готового решения- называй как хочешь. Я отправлял эту задачу, но у меня слишком мало балов. я прошу помощи, не заставляя. Что здесь плохого?
2. помощи хочу. как я могу предоставить свой вариант решения, если на моем очень мало балов???

@dondublon · 20.08.2021, 14:33

Млин, почему везде минусы? Деление с остатком же!

@Catstail · 20.08.2021, 15:14

dondublon, так в формулировке...

@Viktorrus · 20.08.2021, 16:15

Сообщение от cool99999

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

Она правильная, если дает правильный ответ, а не частично правильная.
Одну и ту же задачу на питоне можно решать разными способами. Просто тестирующая программа не правильная, которая принимает только ограниченное количество вариантов решения, а не ориентируется на правильный ответ.

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@cool99999 0 / 0 / 0 Регистрация: 13.08.2021 Сообщений: 18

	Алгоритм Евклида 19.08.2021, 15:13. Показов 15747. Ответов 30 Метки python 3.9 (Все метки) Андрей недавно начал изучать информатику. Одним из первых алгоритмов, который он изучил, был алгоритм Евклида для нахождения наибольшего общего делителя (НОД) двух чисел. Напомним, что наибольшим общим делителем двух чисел a и b называется наибольшее натуральное число x, такое, что и число a, и число b делится на него без остатка. Алгоритм Евклида заключается в следующем: 1.Пусть a, b — числа, НОД которых надо найти. 2.Если b = 0, то число a — искомый НОД. 3.Если b > a, то необходимо поменять местами числа a и b. 4. Присвоить числу a значение a – b. 5.Вернуться к шагу 2. Андрей достаточно быстро освоил алгоритм Евклида и вычислил с его помощью много наибольших общих делителей. Поняв, что надо дальше совершенствоваться, ему пришла идея решить новую задачу. Пусть заданы числа a, b, c и d. Требуется узнать, наступит ли в процессе реализации алгоритма Евклида для заданной пары чисел (a, b) такой момент, когда перед исполнением шага 2 число a будет равно c, а число b будет равно d. Требуется написать программу, которая решает эту задачу. Входные данные Первая строка входных данных содержит количество наборов входных данных K (1 ≤ K ≤ 100). Далее идут описания этих наборов. Каждое описание состоит из двух строк. Первая из них содержит два целых числа: a, b (1 ≤ a, b ≤ 10¹⁸). Вторая строка – два целых числа: c, d (1 ≤ c, d ≤ 10¹⁸). Все числа в строках разделены пробелом. Выходные данные Для каждого набора входных данных выведите слово «YES», если в процессе применения алгоритма Евклида к паре чисел (a, b) в какой-то момент получается пара (c, d). В противном случае выведите слово «NO». Примеры входные данные 2 20 10 10 10 10 7 2 4 выходные данные YES NO 0

@cool99999 0 / 0 / 0 Регистрация: 13.08.2021 Сообщений: 18
	19.08.2021, 15:52 [ТС]
	к сожалению нет. 0

@cool99999 0 / 0 / 0 Регистрация: 13.08.2021 Сообщений: 18
	19.08.2021, 17:00 [ТС]
	программа прошла 29 тестов из 92. В тех которые не прошла пишет: Ошибка во время выполнения программы 0

@Gdez 8840 / 4492 / 1864 Регистрация: 27.03.2020 Сообщений: 7,312
	19.08.2021, 22:40
	Catstail, в задаче входные данные "тяжелые"... 1

@Catstail Супер-модератор 38161 / 21096 / 4306 Регистрация: 12.02.2012 Сообщений: 34,683 Записей в блоге: 14
	19.08.2021, 22:42
	Gdez, да, я прохлопал (10¹⁸ - это немало) 0

@cool99999 0 / 0 / 0 Регистрация: 13.08.2021 Сообщений: 18
	20.08.2021, 10:59 [ТС]
	прошло 30 из 92 0

@cool99999 0 / 0 / 0 Регистрация: 13.08.2021 Сообщений: 18
	20.08.2021, 12:40 [ТС]
	82 из 92 правильно. В остальных написано "неправильный ответ" 0

@cool99999 0 / 0 / 0 Регистрация: 13.08.2021 Сообщений: 18
	20.08.2021, 13:25 [ТС]
	1. может. 2. решения частично правильные. Ну так если программа не проходит все тесты, значит она частично правильная. 3. так проблема изначально была моя. Я попросил помощи у профи. Что здесь плохого? 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	20.08.2021, 13:27
	В 5й строке нужно ещё одно условие добавить 0

@cool99999 0 / 0 / 0 Регистрация: 13.08.2021 Сообщений: 18
	20.08.2021, 13:37 [ТС]
	какое? 0

@cool99999 0 / 0 / 0 Регистрация: 13.08.2021 Сообщений: 18
	20.08.2021, 14:00 [ТС]
	1. для помощи или для лентяев, которые самостоятельно ничего не могут и хотят готового решения- называй как хочешь. Я отправлял эту задачу, но у меня слишком мало балов. я прошу помощи, не заставляя. Что здесь плохого? 2. помощи хочу. как я могу предоставить свой вариант решения, если на моем очень мало балов??? 0

@dondublon 4649 / 2069 / 366 Регистрация: 17.03.2012 Сообщений: 10,176 Записей в блоге: 6
	20.08.2021, 14:33
	Млин, почему везде минусы? Деление с остатком же! 0

@Catstail Супер-модератор 38161 / 21096 / 4306 Регистрация: 12.02.2012 Сообщений: 34,683 Записей в блоге: 14
	20.08.2021, 15:14
	dondublon, так в формулировке... 0