Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

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

(Время: 1 сек. Память: 16 Мб Сложность: 40%)

Дима недавно начал изучать информатику. Одним из первых алгоритмов, который он изучил, был алгоритм Евклида для нахождения наибольшего общего делителя (НОД) двух чисел. Напомним, что наибольшим общим делителем двух чисел 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) такой момент, когда число a будет равно c, а число b будет равно d.

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

Входные данные

Первая строка входного файла INPUT.TXT содержит количество наборов входных данных k (1 ≤ k ≤ 100). Далее идут описания этих наборов. Каждое описание состоит из двух строк. Первая из них содержит два целых числа: a, b (1 ≤ a, b ≤ 1018). Вторая строка – два целых числа: c, d (1 ≤ c, d ≤ 1018).

Выходные данные

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

Пример

INPUT.TXTOUTPUT.TXT
12
20 10
10 10
10 7
2 4
YES
NO

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483



Cейфы TECHNOMAX. На сайте http://privatsafe.ru можно купить сейф для хранения документов в офисе.