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

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

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

• на нем есть два кодовых механизма, первый из которых изначально указывает на число \(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-я комнаты. СЭС не потерпит беспорядка, поэтому все переезды корректны (в каждую комнату переедет ровно одна комната).

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