README.md

Математика

A. Массовая проверка простоты

ограничение по времени на тест: 1.5 секунд

ограничение по памяти на тест: 256 мегабайт

ввод: стандартный ввод

вывод: стандартный вывод

Целое число p ≥ 2 является простым, если у него нет делителей кроме 1 и p. Необходимо для всех чисел во входном файле проверить простые они или нет.

Входные данные

В первой строке задано число n (2 ≤ n ≤ 500000). В следующих n строках заданы числа ai (2 ≤ ai ≤ 2*10^7), которые нужно проверить на простоту

Выходные данные

Для каждого числа во входном файле выведите на отдельной строке «YES» или «NO» в зависимости от того, простое оно или нет.

Примеры

входные данные

4
60
14
3
55

выходные данные

NO
NO
YES
NO

Решение

B. Массовое разложение на множители

ограничение по времени на тест: 0.5 секунд

ограничение по памяти на тест: 64 мегабайта

ввод: стандартный ввод

вывод: стандартный вывод

Дано много чисел. Требуется разложить их все на простые множители.

Входные данные

В первой строке задано число n (2 ≤ n ≤ 300000). В следующих n строках заданы числа ai (2 ≤ ai ≤ 10^6), которые нужно разложить на множители.

Выходные данные

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

Примеры

входные данные

4
60
14
3
55

выходные данные

2 2 3 5 
2 7 
3 
5 11 

Решение

C. Большая проверка на простоту

ограничение по времени на тест: 2 секунды

ограничение по памяти на тест: 64 мегабайта

ввод: стандартный ввод

вывод: стандартный вывод

Дано n натуральных чисел ai. Определите для каждого числа, является ли оно простым.

Входные данные

Программа получает на вход число n, 1 ≤ n ≤ 1000 и далее n чисел ai, 1 ≤ ai ≤ 10^18.

Выходные данные

Если число ai простое, программа должна вывести YES, для составного числа программа должна вывести NO.

Примеры

входные данные

4
1
5
10
239

выходные данные

NO
YES
NO
YES

Решение

D. Китайская теорема

ограничение по времени на тест: 2 секунды

ограничение по памяти на тест: 64 мегабайта

ввод: стандартный ввод

вывод: стандартный вывод

Решите в целых числах систему уравнений

    x = a (mod n)
    x = b (mod n)

Гарантируется, что n и m взаимно просты. Среди решений следует выбрать наименьшее неотрицательное число.

Входные данные

Входной файл содержит четыре целых числа a, b, n и m (1 ≤ n, m ≤ 10^6, 0 ≤ a < n, 0 ≤ b < m).

Выходные данные

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

Примеры

входные данные

1 0 2 3

выходные данные

3

входные данные

3 2 5 9

выходные данные

38

Решение

E. Взлом RSA

ограничение по времени на тест: 2 секунды

ограничение по памяти на тест: 64 мегабайта

ввод: стандартный ввод

вывод: стандартный вывод

В 1977 году Ronald Linn Rivest, Adi Shamir и Leonard Adleman предложили новую криптографическую схему RSA, используемую до сих пор. RSA является криптосистемой с открытым ключом: зашифровать сообщение может кто угодно, знающий общеизвестный открытый ключ, а расшифровать сообщение — только тот, кто знает специальный секретный ключ.

Желающий использовать систему RSA для получения сообщений должен сгенерировать два простых числа p и q, вычислить n = pq и сгенерировать два числа e и d такие, что {ed ≡ 1 ± od{(p - 1)(q - 1)}} (заметим, что {(p - 1)(q - 1) = φ(n)}). Числа n и e составляют открытый ключ и являются общеизвестными. Число d является секретным ключом, также необходимо хранить в тайне и разложение числа n на простые множители, так как это позволяет вычислить секретный ключ d.

Сообщениями в системе RSA являются числа из Z. Пусть M — исходное сообщение. Для его шифрования вычисляется значение C = M^e mod n (для этого необходимо только знание открытого ключа). Полученное зашифрованное сообщение C передается по каналу связи. Для его расшифровки необходимо вычислить значение M = C^d mod n, а для этого необходимо знание секретного ключа.

Вы перехватили зашифрованное сообщение C и знаете только открытый ключ: числа n и e. "Взломайте" RSA — расшифруйте сообщение на основе только этих данных.

Входные данные

Программа получает на вход три натуральных числа: n, e, C, n ≤ 10^9, e ≤ 10^9, C < n. Числа n и e являются частью какой-то реальной схемы RSA, т.е. n является произведением двух простых и e взаимно просто с φ(n). Число C является результатом шифрования некоторого сообщения M.

Выходные данные

Выведите одно число M (0 ≤ M < n), которое было зашифровано такой криптосхемой.

Примеры

входные данные

143
113
41

выходные данные

123

входные данные

9173503
3
4051753

выходные данные

111111

Решение

F. Задача для второклассника

ограничение по времени на тест: 2 секунды

ограничение по памяти на тест: 256 мегабайт

ввод: стандартный ввод

вывод: стандартный вывод

Вам даны два числа. Необходимо найти их произведение.

Входные данные

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

Выходные данные

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

Примеры

входные данные

2
2

выходные данные

4

входные данные

1
-1

выходные данные

-1

Решение