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

@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

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

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

Новые блоги и статьи Все статьи Все блоги /
Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

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

	Алгоритм Евклида 19.08.2021, 15:13. Показов 15984. Ответов 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 8850 / 4501 / 1864 Регистрация: 27.03.2020 Сообщений: 7,316
	19.08.2021, 22:40
	Catstail, в задаче входные данные "тяжелые"... 1

@Catstail Супер-модератор 38173 / 21108 / 4307 Регистрация: 12.02.2012 Сообщений: 34,710 Записей в блоге: 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 4652 / 2072 / 366 Регистрация: 17.03.2012 Сообщений: 10,182 Записей в блоге: 6
	20.08.2021, 14:33
	Млин, почему везде минусы? Деление с остатком же! 0

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