НОД и алгоритм Евклида

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

Замок на двери подвала устроен следующим образом:

• на нем есть два кодовых механизма, первый из которых изначально указывает на число \(a\), а второй — на число \(b\);

• первый кодовый механизм сломан, поэтому изменить значение \(a\) нельзя;

• второй кодовый механизм можно вращать только в одном направлении, тем самым увеличивая значение \(b\);

• замок открывается тогда и только тогда, когда существует целое число \(d > 1\), делящее и \(a\), и \(b\) (иными словами, когда у \(a\) и \(b\) есть общий делитель больше единицы).

За одну секунду Эрен может повернуть второй кодовый механизм так, что \(b\) увеличится ровно на \(1\). Определите, за какое минимальное время Эрен сможет открыть подвал.

Формат входных данных
В первой строке дано единственное целое число \(t\) — количество тестовых случаев \((1 \leqslant t \leqslant 1000)\).

В \(i\)-й из следующих \(t\) строк через пробел даны два целых числа \(a_i\) и \(b_i\) — начальные значения, на которые указывают кодовые механизмы в \(i\)-м тесте (\(2 \leqslant a_i, b_i \leqslant 10^9\)).

Формат выходных данных
Для каждого теста выведите в отдельной строке минимальное время, за которое Эрен откроет подвал.

 

Дано натуральное число N. Требуется представить его в виде суммы двух натуральных чисел A и B таких, что НОД (наибольший общий делитель) чисел A и B — максимален.

Ограничение по времени выполнения программы - 1 секунда, ограничение по используемой памяти - 64 мегабайта.

Входные данные
Во входных данных записано натуральное число N (2 ≤ N ≤ 10⁹)

Выходные данные
Выведите два искомых числа A и B. Если решений несколько, выведите любое из них.

Напишите программу, реализующую сложение, вычитание, умножение и деление дробей. Формат дробей во входных и выходных данных:

• знак числа (пишется только в случае, когда его отсутствие изменяет число);
• целая часть числа (нулевая целая часть не пишется, если есть числитель и знаменатель);
• пробел (не пишется, если отсутствует целая или дробная часть);
• числитель (если он не равен нулю);
• знак / (если есть числитель);
• знаменатель (если есть числитель).

Примеры представления дробных чисел: -7 3/4, 8 1/2, -7/11, 0, 11.

Ограничения (как на входные, так и на выходные данные): целая часть может принимать значения из диапазона 0...30 000, числитель и знаменатель могут принимать значения от 1 до 30 000, при делении второй операнд не равен нулю.

Входные данные
В первой строке вводится дробь (первый операнд), во второй - знак операции ("+" - сложение, "-" - вычитание, "*" - умножение, "/" - деление), в третьей строке - дробь (второй операнд). Обе дроби могут быть сократимы.

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

Многоугольник на плоскости задан целочисленными координатами своих N вершин в декартовой системе координат. Требуется найти количество точек с целочисленными координатами, лежащих на границе многоугольника. Стороны многоугольника друг с другом не соприкасаются (за исключением соседних - в вершинах) и не пересекаются.

Ограничения: 3 <= N <= 100 000, координаты вершин целые и по модулю не превосходят 1 000 000 000.

Входные данные
В первой строке содержится число N, в следующих N строках - пары чисел - координаты точек. Если соединить точки в данном порядке, а также соединить первую и последнюю точки, получится заданный многоугольник.

Выходные данные
Вывести одно число - количество точек с целочисленными координатами на границе многоугольника.

Ребята во дворе решили поиграть в прятки. Чтобы выбрать ведущего, который будет искать, они решили воспользоваться считалкой. Считалка состоит из \(k\) слов, и используется следующим образом.

Все \(n\) ребят становятся в круг и один из них, начиная с себя, по очереди указывает на ребят в порядке, в котором они стоят по кругу, называя слова считалки. Тот, на кого указывает считающий, называя последнее слово считалки, выбывает из круга. После этого считалка повторяется сначала, а счет начинается со следующего за выбывшим. Так продолжается до тех пор, пока в круге не останется один человек. Он то и будет ведущим.

Но на этот раз ребята так увлеклись идеей предстоящей игры, что забывали выходить из круга, после того как считающий указывал на них, называя последнее слово считалки. В результате считающий снова указывал на них при следующих повторениях считалки.

Ребята заметили это только тогда, когда после очередного повторения считалки считающий снова указал на последнем слове на участника, который уже должен был покинуть круг. Теперь их заинтересовал вопрос — а на скольких ребят в этот момент считающий все еще не указал, что они должны покинуть круг.

Помогите им ответить на этот вопрос.

Формат входных данных
Строка содержит два целых числа — \(n\) и \(k\) (\(1 \le n \le 1000\), \(1 \le k \le 10^9\)).

Формат выходных данных
Выведите одно число — количество ребят, на которых ведущий, еще не указал, что они должны покинуть круг, когда ведущий повторно укажет на кого-либо на последнем слове считалки.

В ЛКШ Витя решил переселять комнаты каждый месяц. Известно какая комната в какую переезжает. Требуется определить целое число лет, которое пройдет прежде чем все окажутся снова в своих комнатах.

Входные данные
В первой строке записано N - количество комнат (1 < N < 101) и далее номера комнат, в которые переезжают 1,2,3,..,N-я комнаты. СЭС не потерпит беспорядка, поэтому все переезды корректны (в каждую комнату переедет ровно одна комната).

Выходные данные
Выведите количество лет, которое пройдет, прежде чем все снова окажутся в своих комнатах

Ипполит Матвеевич Воробьянинов ходит вдоль улицы из \(n\) домов, пронумерованных числами от \(1\) до \(n\), и расклеивает афиши. Сначала он наклеил афиши на каждый дом, номер которого делился без остатка на \(a\). Поскольку афиш осталось еще много, вторым проходом он наклеил афиши на каждый дом, номер которого делился без остатка на \(b\). При этом, если на доме уже была наклеена афиша, новую Воробьянинов не клеил. Сколько всего афиш расклеил бывший предводитель дворянства?

Формат входных данных
Три строки содержат три натуральных числа: \(n\) — количество домов на улице, \(a\) и \(b\) — выбранные Воробьяниновым числа. Все числа не превосходят \(10^9\).

Формат выходных данных
Выведите одно неотрицательное целое число — количество расклеенных афиш.

Замечание
В первом примере на улице \(10\) домов. Ипполит Матвеевич первым проходом расклеил пять афиш на дома, номера которых делятся на \(2\), то есть на дома с номерами \(2\), \(4\), \(6\), \(8\), \(10\). Вторым проходом он расклеил две афиши на дома, номера которых делятся на \(3\), то есть на дома с номерами \(3\) и \(9\). Дом номер \(6\) он пропустил — на нем афиша уже висит. Всего наклеено \(7\) афиш.

Во втором примере Воробьянинов не наклеит ни одной афиши.

Будем называть два натуральных числа \(x\) и \(y\) непохожими, если они различны и нет двух различных отличных от \(1\) чисел \(a\) и \(b\), таких, что и \(x\) и \(y\) делятся как на \(a\), так и на \(b\). Например, 6 и 9 непохожи, так как единственное число, отличное от 1, на которое делятся оба числа "— 3. А вот числа 12 и 18 не являются непохожими, так как оба делятся на 2, 3 и 6.

Задано натуральное число \(x\), а также натуральные числа \(l\) и \(r\). Требуется найти все числа \(y\), такие что \(l \le y \le r\), и числа \(x\) и \(y\) непохожи.

Формат входных данных
На первой строке ввода задано число \(x\) (\(1 \le x \le 10^9\)).

На второй строке ввода задано число \(l\), на третьей строке ввода задано число \(r\) (\(1 \le l \le r \le 10^9\); \(r - l \le 1000\)).

Формат выходных данных
На первой строке выведите число \(k\) "— количество непохожих на \(x\) чисел на отрезке от \(l\) до \(r\), включительно.

На второй строке выведите все эти числа в возрастающем порядке.

У Деда Мороза есть N мешков с подарками. Каждый мешок имеет вес a1, a2, ..., aN. Для равномерной нагрузки на сани Деду Морозу необходимо, чтобы вес всех мешков был одинаковым. Чтобы этого добиться, Дед Мороз своим волшебным посохом может выполнить одну из следующих операций любое количество раз, возможно ноль раз.

• Дед Мороз может выбрать любой мешок и если его вес кратен двум, то уменьшить вес в два раза.
• Дед Мороз может выбрать любой мешок и если его кратен трем, то уменьшить вес в три раза.

На каждую операцию у Деда Мороза уходит 1 секунда.

Найдите минимальное общее количество секунд, которое необходимо Деду Морозу, для достижения одинакового веса всех мешков с подарками. Если нет способа достичь цели, выведите вместо этого значение -1.

Входные данные
Программа получает на вход в первой строке целое число N (2 <= N <= 1000). Во второй строке записаны N чисел ai - вес i-го мешка с подарками (1 <= ai <= 10⁹).


Выходные данные
Выведите ответ на задачу.
 
 

Примеры

№	Входные данные	Выходные данные
1	3 1 4 3	3
2	3 2 7 6	-1
3	6 1 1 1 1 1 1	0

Был обычный будний вечер в Магнитогорске. Фил и Космос возвращались на машине домой после тяжёлой рабочей смены. Тут Космос вспомнил, что Белый дал ему задание, которое он благополучно забыл выполнить. Чтобы уберечь Космоса от гнева Саши Белого, помогите ему выполнить задание.
Даны n целых чисел a₁,a₂,...,a_n. Требуется сделать наибольший общий делитель (НОД) всех чисел массива равным 1. За одну операцию можно сделать следующее:
•    Выбрать произвольный индекс в массиве 1 <= i <= n;
•    Сделать a_i = gcd(a_i,i). Стоимость такой операции равна n − i + 1.
Требуется найти минимальную суммарную стоимость операций, которые нужно будет сделать, чтобы НОД чисел массива стал равен 1.
Входные данные
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число t (1 <= t <= 5000) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит единственное целое число n (1 <= n <= 20) — длину массива.
Вторая строка каждого набора входных данных содержит n целых чисел a₁,a₂,...,a_n (1 <= a_i <= 10⁹) — элементы массива.
Выходные данные
Для каждого набора входных данных выведите единственное целое число — минимальную суммарную стоимость операций, которые нужно будет сделать, чтобы НОД чисел массива стал равен 1.
 

Примеры

№	Входные данные	Выходные данные
1	7 1 1 1 2 2 2 4 3 3 6 9 4 5 10 15 20 5 120 60 80 40 80 6 150 90 180 120 60 30	0 1 2 2 1 3 3

Замечание
В первом наборе входных данных НОД всего массива уже равен 1, поэтому операции применять не нужно.
Во втором наборе входных данных выберем i = 1. После этой операции a1 = gcd(2,1) = 1. Стоимость этой операции была равна 1.
В третьем наборе входных данных нужно будет выбрать i = 1, после этого массив a будет равен [1,4]. НОД этого массива равен 1, а суммарная стоимость равна 2.
В четвертом наборе входных данных нужно выбрать i = 2, после этого массив a будет равен [3,2,9]. НОД этого массива равен 1, а суммарная стоимость равна 2.
В шестом наборе входных данных можно выбрать i = 3, после этого массив a будет равен [120,60,1,40,80]. НОД этого массива равен 1, а суммарная стоимость равна 3.
 

Громозека и Алиса старые друзья. Встречаясь на какой-то планете, они постоянно заходят в кафе. Но Алиса не любит заходить в каждое a-ое кафе, а Громозека в каждое g-ое кафе. Чтобы никого не обидеть, они не заходят в те кафе, в которые не хотят заходить одновременно и Алиса и Громозека. На очередной прогулке у них на пути N кафе. Во сколько кафе они смогут зайти?

Входные данные
Единственная строка содержит три целых числа - a , g , N ( 1 <= a , g , N <= 10⁹ ).

Выходные данные
Выведите единственное число - количество кафе, в которые смогут зайти Громозека и Алиса.
 

Примеры

№	Входные данные	Выходные данные
1	1 1 10	0
2	1 2 5	3

Наибольшим общим делителем непустого набора натуральных чисел A называется максимальное натуральное число d, такое что оно является одновременно делителем всех чисел множества A.
Задан массив натуральных чисел [a₁, a₂, . . . , a_n] и число k. Требуется выбрать в нем подмассив из k подряд идущих элементов [a_l, a_l+1, . . . , a_l+k−1], чтобы их наибольший общий делитель был как можно больше, и вывести этот наибольший общий делитель.

Входные данные
Первая строка ввода содержит два целых числа n и k (2 ≤ n ≤ 500 000, 2 ≤ k ≤ n).
Вторая строка содержит n натуральных чисел a₁, a₂, . . . , a_n (1 ≤ a_i ≤ 10¹⁸).

Выходные данные
Выведите одно натуральное число — максимальное возможное значение наибольшего общего делителя элементов подмассива длины k заданного массива.

Примеры

№	Входные данные	Выходные данные
1	10 4 2 3 4 8 12 6 12 18 4 3	6

Марья Ивановна с Марьей Михайловной привели школьников в кинотеатр. Чтобы не было никаких обид, Марья Ивановна построила всех школьников по алфавиту и рассадила их: сначала в первый ряд слева направо, затем во второй слева направо и т.д., заполнив весь зал из n рядов по m кресел. Тут пришла Марья Михайловна и сказала, что ребята сели неправильно – надо пересесть. Она предложила сначала заполнить все первые места от первого ряда к последнему, затем все вторые места и т. д.

Определите, сколько школьников после такой пересадки останется на своем месте.

Например, если n = 3 и m = 3, то в первом случае дети сядут так:

1    2    3
4    5    6
7    8    9
а во втором – так:
1    4    7
2    5    8
3    6    9
Таким образом, три школьника: 1, 5 и 9 останутся на своих местах.

Входные данные
Вводятся два целых числа n и m (1 ≤ n, m ≤ 10⁹ ).

Выходные данные
Выведите количество школьников, которые останутся на своих местах.
 

Примеры

№	Входные данные	Выходные данные
1	3 3	3
2	2 4	2

У Громозеки есть N часов. Стрелка i-х часов (\(1<=i<=N\)) поворачивается на 360 ° ровно за Ti секунд. Изначально стрелка всех часов стоит на месте и направлена прямо вверх. Громозека запускает все часы одновременно. Через сколько секунд стрелка всех часов снова укажет прямо вверх?

Входные данные
В первой строке записано целое число N (\(1<=N<=100\)). В следующих N строках записаны целые числа Ti (\(1<=T_i<=10^{18}\)), по одному числу в строке. 

Выходные данные
Выведите на экран ответ. Гарантируется, что ответ не превышает \(10^{18}\).
 

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 2 3	6	У нас есть двое часов. Время, когда стрелка каждых часов указывает вверх, выглядит следующим образом: Часы 1: 2, 4, 6, ... секунд после начала. Часы 2: 3, 6, 9, ... секунд после начала. Таким образом, требуется 6 секунд, пока стрелки обоих часов снова не укажут прямо вверх.
2	5 2 5 10 1000000000000000000 1000000000000000000	1000000000000000000

 

Многоугольник (не обязательно выпуклый) на плоскости задан координатами своих вершин. Требуется подсчитать количество точек с целочисленными координатами, лежащих внутри него (но не на его границе).

Формат входных данных
    В первой строке содержится N (3 ≤N ≤1000) – число вершин многоугольника. В последующих N строках идут координаты (X_i, Y_i) вершин многоугольника в порядке обхода по часовой стрелке. X_i и Y_i - целые числа, по модулю не превосходящие 1000000.

Формат выходных данных
Вывести одно число – искомое число точек.

Примеры

№	Входные данные	Выходные данные
1	4 -1 -1 -1 1 1 1 1 -1	1
2	3 0 0 0 2 2 0	0

На клетчатой бумаге Петя нарисовал отрезок из точки с координатами (a,b) в точку с координатами (c,d). Через сколько клеток проходит этот отрезок (считается, что отрезок проходит через клетку, если он проходит через ее внутренность, если же он проходит только через вершину или по границе клетки, считается, что он не проходит через клетку).

Входные данные
Вводятся целые числа a, b, c, d. Числа по модулю не превышают 10⁹.

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

Примеры

№	Входные данные	Выходные данные
1	0 0 6 4	8
2	3 3 -3 3	0

В Берляндии плачевная ситуация с междугородним автобусным сообщением. Во всей стране есть всего три автобусных маршрута, по каждому из которых курсирует лишь один автобус. В первый день нового года ровно в полночь все три автобуса отправляются по своим маршрутам из столицы Берляндии. Известно, что первому автобусу на то, чтобы проехать весь маршрут и вернуться в столицу требуется a минут, второму — b минут, а третьему — c минут. Таким образом, первый автобус отправляется из столицы Берляндии в моменты времени 0, a, 2a, 3a , второй — в моменты времени 0, b, 2b, 3b , а третий в моменты времени 0, c, 2c, 3c .

Момент времени называется подходящим для пересадки , если в этот момент все три автобуса отправляются из столицы Берляндии. Например если a=1, b=2, c=1, то моменты времени 0 и 2 являются подходящими для пересадки, а момент времени 1 не является, потому что в этот момент времени второй автобус находится в пути. Берляндия — особая страна с особым измерением времени, поэтому в берляндских сутках ровно t минут. Это означает, что в первый день происходят все моменты времени с 0-го по (t−1)-й включительно, во второй день — c t-го по (2t−1)-й включительно, в третий — с 2t-го по (3t−1)-й включительно и так далее.

Министерство транспорта Берляндии заинтересовалось, сколько подходящих для пересадки моментов времени произойдёт в d-й день в Берляндии. К сожалению, местные чиновники заняты другими делами, поэтому ответить на этот вопрос было поручено вам.

Входные данные
В пяти строках заданы пять целых чисел a, b, c, t  и d (1≤a, b, c≤10⁶ , 1≤t, d≤10⁹ ) — время полного прохождения маршрута первым, вторым и третьим автобусами, соответственно, количество минут в сутках и номер дня, которым интересуется министерство транспорта Берляндии.

Выходные данные
Выведите одно целое число — количество подходящих для пересадки моментов времени в d-й день.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	1 2 1 3 1	2	Сутки длятся 3 минуты, поэтому все моменты времени в день с номером 1 — это 0, 1, 2, из них моменты времени 0 и 2 являются подходящими для пересадки
2	2 3 4 7 2	1	Здесь рассматриваются вторые сутки с моментами времени 7, 8, 9, 10, 11, 12, 13. Первый автобус отправляется в моменты времени 8, 10, 12, второй автобус — в моменты времени 9 и 12, а третий — в моменты времени 8 и 12. Таким образом, только момент времени 12 является подходящим для пересадки.
3	2 3 4 3 3	0	Нет ни одного подходящего для пересадки момента времени

Приближалось лето, и Игорь, Гена и Денис решили пойти вместе в поход, как и в прошлом году. Почти все вопросы уже были решены: уже был проработан маршрут, куплены билеты на поезд, в шкафу у Дениса найдена четырехместная палатка, а под кроватью у Игоря — топор. Осталось решить только вопрос с продуктами.

В прошлом году ребята честно признались, что не знают, сколько им нужно продуктов, и попросили помочь свою одноклассницу Настю, которая составила им список покупок. Но в этом году снова спрашивать у нее уже как-то несолидно. Можно было бы посмотреть, сколько они покупали в прошлом году, и взять столько же, но ни у кого из ребят не сохранилось ни чеков, ни списка продуктов.

Зато у них сохранилась переписка в социальной сети, где они спорили, кто сколько банок тушенки понесет. В этой переписке Игорь сначала предложил поделить всю тушенку в отношении a: b: c, так, что первую часть понесет сам Игорь, вторую — Гена, а третью — Денис. Но Денису это не понравилось, и он предложил поменять соотношение на d: e: f.

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

По данным двум отношениям a: b: c и d: e: f вычислите, сколько банок тушенки ребята покупали для прошлогоднего похода. Из всех возможных ответов выведите минимальный. Ребята помнят, что как минимум одна банка тушенки у них точно была.

Входные данные
В первой строке даны три целых положительных числа a, b, c, разделенные пробелами. Во второй строке даны три целых положительных числа d, e, f, также разделенные пробелами.

Все числа не превышают 1000.

Выходные данные
Выведите целое положительное число — количество банок тушенки.
 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	10 3 7 3 1 1	20	При делении тушенки между ребятами в отношении 10:3:7 Игорь понесет 10 банок, Гена — 3 банки, а Денис — 7 банок. А в случае соотношения 3:1:1 Игорю достанется 12 банок, а Гене и Денису по 4.

Некоторые уроки в школе для Вани и Пети  очень скучны. На этих уроках Петя и Ваня придумали игру. Сначала мальчики записывают на листке два различных натуральных числа a и b .
Ход игры заключается в следующем: среди записанных чисел выбирают p и q такие, что модуля их разности \(| p - q |\) еще нет на листке, и дописывают его.
Проигрывает тот, кто не может сделать ход.
Определите, кто из ребят окажется победителем при правильной игре обоих. Ваня вежливый мальчик, поэтому всегда ходит вторым.

Входные данные: В первой и единственной строке записано два различных натуральных числа 1 <= a , b <= 10^9 , разделенные пробелом - два исходных числа на листке.

Выходные данные: Выведите имя победителя в этой игре (Petya или Vanya)

Примечание: В первом примере Петя первым ходом допишет на листок число |6−2| = 4 . Больше ходов нет, поэтому выигрывает Петя. Во втором примере первым ходом на листок будет дописано число |4−1| = 3 . Затем Ваня может записать |3−1| = 2 , тогда у Пети ходов не останется. Побеждает Ваня.

Примеры

№	Входные данные	Выходные данные
1	6 2	Petya
2	4 1	Vanya