Темы --> Информатика --> Алгоритмы --> Арифметические алгоритмы
    НОД и алгоритм Евклида(45 задач)
    Системы счисления(36 задач)
    "Длинная" арифметика(58 задач)
    Простые числа и разложение на множители(45 задач)
    Остатки(21 задач)
    Быстрое возведение в степень(3 задач)
    Быстрое преобразование Фурье(3 задач)
---> 2 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников --> Региональный этап --> Московская областная олимпиада
    2007(7 задач)
    2008(6 задач)
Страница: 1 Отображать по:
#1222
Алгоритм Евклида
  

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

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

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

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

Примеры
Входные данные
2
20 10
10 10
10 7
2 4
Выходные данные
YES
NO
#3140
Феодальные отношения
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Во Флатландии с некоторых пор процветают феодальные отношения – у каждого порядочного феодала есть ровно два вассала, у непорядочных – вассалов нет совсем. Каждый феодал строит свой замок в городе на прямой, при этом:

  • высота замка (всегда целое положительное число) должна быть строго больше высот замков его вассалов (для соблюдения субординации).
  • замки первого из двух вассалов и всех вассалов этого вассала должны быть построены слева, второго вассала и его вассалов – справа (для пресечения междоусобиц). Это правило должно выполняться для всех
  • высота замка должна быть минимально возможной (для экономии ресурсов)
  • число всех подчиненных (непосредственно или через промежуточных) у правого и левого вассалов одинаково (для баланса сил).

Для удобства замки феодалов занумерованы натуральными числами по порядку слева направо, начиная с единицы, и разбиты на улицы. Улица (i, j) представляет собой последовательность подряд идущих замков, начиная с замка под номером i и заканчивая замком с номером j (i ≤ j)

Однажды в город приехал новый феодал и пожелал выкупить там замок у одного из жителей. Также ему стало интересно узнать социальный статус соседей по улице, однако, город к тому времени так разросся, что феодал уже не мог сделать этого самостоятельно. Напишите программу, которая поможет ему!

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

Первая строка входного файла содержит число N (1 ≤ N ≤ 30000) — высота замка единственного главного феодала в городе, который никому не подчиняется. Далее, в следующих двух строках идут числа i и j (\(0 \leq i, j < 10^{10000}\)), задающие улицу (i, j), на которой хочет приобрести замок новый феодал (гарантируется, что замки с номерами i и j находятся в черте города, i ≤ j, j – i ≤ 105).

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

Примечание

Будут оцениваться и частичные решения задачи при малых N. Частичные решения для N<20 набирают до 40 баллов, а для N<50 набирают не более 70 баллов.

Ввод
Вывод
2
1
3
1 2 1
3
3
7
1 3 1 2 1
50
128873293
128873293
1
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест