Задача 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

Problem B. Fractional multiplication ≡

Statement

There is a set of N rational fractions, each is represented by corresponding numerator A_i and denominator B_i.

You must write a program that outputs:

• 0 — if the product of all fractions is either 1 or a prime;
• 1 — if it is integer non-prime;
• 2 — if it is a fractional number.

Input format

Input contains integer N, followed by N pairs of integers (A_i, B_i).

Output format

Output must contain a single integer — answer to the problem.

Constraints

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

Sample tests

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

Problem D. Arithmetic pairs ≡

Statement

Your program must calculate total number of such pairs of integers (p, n) that p ≥ 1, n > 1 и A ≤ pⁿ ≤ B.

Input file format

Input file contains two integers A and B.

Output file format

Output file must contain a single integer — number of pairs.

Constraints

2 ≤ A ≤ B < 2⁶³

Sample tests

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