Задача A. Возведение в степень ≡

Условие

Даны три числа: A, N, P. Требуется возвести число A в степень N по модулю P.

Формат входных данных

Три целых положительных числа: A N P

Формат выходных данных

Выходные данные должны содержать единственное число - A^N

Ограничения

0 < A, N < 2⁶⁴

2 ≤ P < 2³²

Примеры тестов

2 2 3

1

2 4 10

6

5 7 3

2

Задача B. Fractional multiplication ≡

Условие

Имеется набор из N рациональных дробей, каждая из которых задается своим числителем A_i и знаменателем B_i.

Требуется написать программу, которая выводит:

• 0 — если произведение всех этих дробей дает единицу либо простое число;
• 1 — если это составное целое число;
• 2 — если это дробное число.

Формат входных данных

Входные данные содержит целое число N, за которым следует набор из N пар целых чисел (A_i, B_i).

Формат выходных данных

Выходные данные должны содержать единственное число — ответ задачи.

Ограничения

1 ≤ N ≤ 200, 1 ≤ (A_i, B_i) < 2³²

Примеры тестов

1
35880 17940

0

1
76824 12804

1

1
94803 11573

2

Задача C. Степень делителя ≡

Условие

Обозначим за P(A, B) результат произведения всех натуральных чисел от A до B включительно.

Для заданных значений A, B, q требуется определить, с какой степенью число q входит в число P(A, B) (в качестве его делителя)

Формат входных данных

Три целых положительных числа: A B q

Формат выходных данных

Выходные данные должны содержать единственное число x - степень делителя q в числе P(A, B)

Ограничения

0 < A, B < 2⁶⁴

2 ≤ q < 2³²

Примеры тестов

4 7 3

1

9 75 35

10

Задача D. Arithmetic pairs ≡

Условие

Требуется подсчитать общее количество пар целых чисел (p, n) таких, что p ≥ 1, n > 1 и A ≤ pⁿ ≤ B.

Формат входного файла

Входной файл содержит два натуральных числа: A и B.

Формат выходного файла

Выходной файл должен содержать единственное целое число — количество пар.

Ограничения

2 ≤ A ≤ B < 2⁶³

Примеры тестов

10 100

13

37 48

0

Задача E. Наибольший общий делитель ≡

Условие

Дается N чисел. Требуется найти их наибольший общий делитель.

Формат входных данных

Первая строка содержит одно целое число - N

Вторая строка содержит N натуральных чисел a_i, разделенных пробелами

Формат выходных данных

Выходные данные должны содержать единственное число - наибольший общий делитель чисел.

Ограничения

1 ≤ N ≤ 10⁵

1 ≤ a_i < 2⁶⁴

Примеры тестов

2
12 16

4

2
25 9

1

3
12 27 15

3

Задача F. Роковое число 23 ≡

Условие

К юному программисту Васе обратился человек по имени Уолтер Спэрроу и стал утверждать, что любое заданное число n содержит число 23. Уолтер предлагает получить 23 из числа n путем многократного сложения или вычитания его цифр.

Формат входного файла

Входной файл содержит целое число n.

Формат выходного файла

Выходной файл должен содержать строку Yes, если утверждение Уолтера справедливо для заданного числа, и No в противном случае.

Ограничения

1 ≤ n ≤ 10⁵

Примеры тестов

53

Yes

63

No

Задача G. Диофантово уравнение ≡

Условие

Для заданных чисел a, b, c решить диофантово уравнение ax + by = c в целых числах

Формат входных данных

Три целых числа a, b, c, разделенные пробелами

Формат выходных данных

Вывести пару целых чисел (x, y) - решение заданного диофантова уравнения, в котором x минимально возможный неотрицательный. Если таких пар несколько, выведите пару с минимальным неотрицательным y

В случае, если решений не существует, вывести -1

Ограничения

−2³¹ < a, b, c < 2³¹

Примеры тестов

2 3 1

2 -1

6 4 3

-1

0 2 6

0 3