--->
45 задач
<---
Источники
#1391
Темы:
[НОД и алгоритм Евклида]
Источники:
[
Личные олимпиады,
Открытая олимпиада школьников,
2008-2009,
Заключительный этап,
Задача G
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
На каждой из трех осей установлено по одной вращающейся шестеренке и неподвижной стрелке. Шестеренки соединены последовательно. На первой шестеренке n зубцов, на второй — m, на третьей — k. На каждом зубце первой, второй и третьей шестеренок по часовой стрелке написаны в порядке возрастания числа от 1 до n, от 1 до m и от 1 до k соответственно. Стрелки зафиксировали таким образом, что когда стрелка первой оси указывает на число, стрелки двух других осей также указывают на числа. Витя записывает три числа (a1,a2,a3), на которые указывают стрелки. После этого он поворачивает первую шестеренку на угол 360°/n против часовой стрелки, чтобы напротив стрелки на первой оси оказался следующий (по часовой стрелке) зубец. При этом вторая шестеренка поворачивается на угол 360°/m по часовой стрелке (размеры зубцов у шестеренок одинаковые, поэтому размеры самих шестеренок разные, чтобы на границе шестеренок равномерно уложилось разное число одинаковых по размеру зубцов), а третья шестеренка поворачивается на угол 360°/k против часовой стрелки. Витя опять записывает три числа, на которые указывают стрелки.
Поступая и далее таким образом, Витя заметил, что после некоторого количества таких действий стрелки показывают на три первоначальных числа.
Теперь его очень интересует, как по двум данным тройкам чисел определить, принадлежат ли они к одной последовательности, то есть можно ли некоторым количеством поворотов перейти от первой тройки ко второй. Он попросил вас написать программу, которая отвечает на этот вопрос.
Входные данные
В первой строке содержатся четыре числа T, n, m, k (1 ≤ T ≤ 10, 1 ≤ n, m, k ≤ 1018) — количество пар троек, которые хочет проверить Витя и количества зубцов соответственно на первой, второй и третьей шестеренках.
В следующих T строках записаны шесть натуральных чисел a1, a2, a3, b1, b2, b3 (1 ≤ a1, b1 ≤ n, 1 ≤ a2, b2 ≤ m, 1 ≤ a3, b3 ≤ k).
Выходные данные
Для каждой пары троек в выходной файл выведите YES, если обе тройки принадлежат одной последовательности, и NO иначе. Каждое слово должно быть в отдельной строке, в порядке, соответствующем входному файлу.
Комментарии к примерам тестов
1. В первой и второй парах вторая тройка получается из первой за один поворот первой шестеренки против часовой стрелки.
В третьем случае из второй конфигурации просто получить первую опять же одним поворотом первой шестеренки против часовой стрелки.
Очевидно, что тогда из первой можно каким-то образом получить вторую.
2. В первой паре тройки нельзя перевести друг в друга.
Во второй тройки переходят друг в друга при одном повороте.
3. (1, 1, 1) — (семь поворотов первой против часовой стрелки шестеренки) — (1, 4, 2) — (еще семь таких же поворотов) — (1, 2, 3) — (один поворот) — (2, 1, 1)
Частичные ограничения
Первая группа состоит из тестов, в которых произведение nmk ≤ 106.
Вторая группа состоит из тестов, в которых n, m, k ≤ 109.
Примечание
Не гарантируется, что описанную в условии задачи систему шестеренок и стрелок можно реально построить.
Примеры
Входные данные
3 11 13 15 5 5 5 6 4 6 11 13 15 1 12 1 2 13 2 1 1 1
Выходные данные
YES YES YES
Входные данные
2 2 2 2 1 1 1 1 1 2 1 1 1 2 2 2
Выходные данные
NO YES
Входные данные
1 7 5 3 1 1 1 2 1 1
Выходные данные
YES
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Даны две сцепленные шестеренки. У одной шестеренки N зубцов, у другой – K. Требуется найти, какое минимальное число поворотов на один зубчик требуется сделать, чтобы шестеренки вернулись в исходное состояние.
Входные данные
В единственной строке --- два натуральных числа N и K, не превосходящих 10 миллионов.
Выходные данные
Выведите искомое количество зубчиков. Гарантируется, что оно не более миллиарда.
Примеры
Входные данные
2 3
Выходные данные
6
Входные данные
6 21
Выходные данные
42
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Дано N чисел. Найти самое большое число, на которое делятся все N чисел.
Входные данные
В первой строке дано число N. Во второй строке даны через пробел N чисел (1 <= N <= 1000).
Выходные данные
Выведите искомое число
Примеры
Входные данные
1 3
Выходные данные
3
Входные данные
3 9 15 22
Выходные данные
1
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Требуется написать программу, которая вычислит, сколько всего точек с целочисленными координатами принадлежат отрезку.
Входные данные
Даны четыре целых числа – координаты концов отрезка (x1, y1) и (x2, y2). Каждая из координат не превышает по абсолютной величине значения 1000.
Выходные данные
Требуется вывести количество точек отрезка, имеющих целочисленные координаты.
Примеры
Входные данные
1 0 5 0
Выходные данные
5
Входные данные
-1 -2 2 4
Выходные данные
4
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Полоска бумаги имеет размеры A × B. Каждый раз от нее отрезается квадрат максимального размера до тех пор, пока не получится квадрат. Сколько квадратов получится?
Входные данные
Программе даны числа A и B (1 ≤ A, B ≤ 109).
Выходные данные
Требуется вывести количество квадратов.
Примеры
Входные данные
15 3
Выходные данные
5
Входные данные
12 8
Выходные данные
3
Входные данные
5 5
Выходные данные
1
Выбрано
:
|