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

Автор:Известная   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

Ограничения

0 < A, N < 264

2 ≤ P < 232

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

Стандартный вход Стандартный выход
1
2 2 3
1
2
2 4 10
6
3
5 7 3
2

Задача B. Fractional multiplication

Автор:A. Baranov   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 200, 1 ≤ (Ai, Bi) < 232

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

Стандартный вход Стандартный выход
1
1
35880 17940
0
2
1
76824 12804
1
3
1
94803 11573
2

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

Автор:Известная   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

Ограничения

0 < A, B < 264

2 ≤ q < 232

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

Стандартный вход Стандартный выход
1
4 7 3
1
2
9 75 35
10

Задача D. Arithmetic pairs

Автор:A. Baranov   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

Ограничения

2 ≤ A ≤ B < 263

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10 100
13
2
37 48
0

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

Автор:Известная   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 105

1 ≤ ai < 264

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

Стандартный вход Стандартный выход
1
2
12 16
4
2
2
25 9
1
3
3
12 27 15
3

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

Автор:О. Ларькина   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

Например, для числа 52: 5 + 5 + 5 + 5 + 5 − 2 = 23. При этом каждую цифру можно использовать сколько угодно раз или не использовать вообще. Вася очень занят и просит вас подтвердить или опровергнуть утверждение Уолтера.

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

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

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

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

Ограничения

1 ≤ n ≤ 105

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

Входной файл (input.txt) Выходной файл (output.txt)
1
53
Yes
2
63
No

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

Автор:Известная   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

Ограничения

231 < a, b, c < 231

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

Стандартный вход Стандартный выход
1
2 3 1
2 -1
2
6 4 3
-1
3
0 2 6
0 3

0.500s 0.015s 25