Олимпиадный тренинг

Задача . Задача для Пети и Вани


Задача

Темы:

Пятиклассники Петя и Ваня изучили на уроках математики следующий алгоритм Евклида:

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

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

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

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

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

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

Напишите для Маши программу, которая проверит, удовлетворяют ли числа a, b, c, d условиям Маши.

Входные данные: Первая строка входных данных содержит количество наборов входных данных K (\(1 <= K <= 100\)). Далее идут описания этих наборов. Каждое описание состоит из двух строк. Первая из них содержит два целых числа: ab (\(1 <= a,\ b <= 10^{18}\)). Вторая строка – два целых числа: cd (\(1 <= c,\ d <= 10^{18}\)).
Все числа в строках разделены пробелом.

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

 

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

 


time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w644
Python73
Комментарий учителя