Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Проверка на простоту#33571

Проверьте, является ли число простым.

Входные данные
Вводится одно натуральное число n не превышающее 2000000000 и не равное 1.

Выходные данные
Необходимо вывести строку prime, если число простое, или composite, если число составное.

Примеры

№	Входные данные	Выходные данные
1	5	prime

Простые числа и разложение на множители

✓ 1 019✗ 2 995300лёгкаяВойти и решать

Последовательность#33303

Последовательность 011212201220200112… строится следующим образом: сначала пишется 0, затем повторяется следующее действие: уже написанную часть приписывают справа с заменой 0 на 1, 1 на 2, 2 на 0, и т.д.

Требуется написать программу, которая по заданному натуральному числу N определяет, какое число стоит на N-ом месте.

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

Дано натурально число число N (1 ≤ N ≤ 10¹⁸).

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

Выведите число, которое стоит на k-ом месте в последовательности.

Ввод	Вывод
1	0
10	2

Арифметические алгоритмы (Теория чисел)Рекурсия Целые числа

✓ 4✗ 301 000средняяВойти и решать

Лесопилка#33135

Недавно на лесопилку, где работает Вася, поступил новый заказ. Для постройки нового дома мэру соседнего города требуется a досок длины x футов и b досок длины y футов.

Поскольку на лесопилке имеется только неограниченный запас досок длины z футов, Васе поручили исполнить заказ клиента, распилив имеющиеся доски на меньшие. Вася хочет закончить работу как можно быстрее, поэтому он хочет выполнить заказ, сделав как можно меньше распилов. При этом количество использованных досок длины z роли не играет, кроме того, часть досок, образовавшихся в результате распила, может не требоваться для заказа и остаться на лесопилке.

Например, если на лесопилке имеются доски длины 80, а клиенту требуется две доски длины 30 и семь досок длины 20, то достаточно сделать семь распилов: одну доску распилить двумя распилами на доски длины 20, 30 и 30, одну тремя распилами на четыре доски длины 20 и одну двумя распилами на доски длины 20, 20 и 40. Доска длины 40 клиенту не нужна, она останется на лесопилке, остальные доски будут отправлены клиенту.

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

На вход программы поступают числа a, x, b, y и z. Все числа положительны и не превышают 300, x<=z, y<=z, x!=y.

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

Выведите минимальное количество распилов, которые требуется сделать для того, чтобы выполнить заказ.

Ввод	Вывод
2 30 7 20 80	7

Динамическое программирование Остатки

✓ 7✗ 43900средняяВойти и решать

Квадраты и кубы#33122

В лаборатории теории чисел одного университета изучают связь между

распределением квадратов и кубов натуральных чисел.

Пусть задано целое неотрицательное число k. Рассмотрим множество натуральных

чисел от a до b, включительно. Будем называть k-плотностью этого множества количество

пар натуральных чисел x и y, таких, что a ≤ x² ≤ b, a ≤ y³ ≤ b, причем |x²– y³| ≤ k.

Например, 2-плотность множества натуральных чисел от 1 до 30 равна 3, так как

подходят следующие пары:

x = 1, y = 1, |x²– y³| = |1 – 1| = 0;

x = 3, y = 2, |x²– y³| = |9 – 8| = 1;

x = 5, y = 3, |x²– y³| = |25 – 27| = 2.

Требуется написать программу, которая по заданным натуральным числам a и b, а

также целому неотрицательному числу k, определяет k-плотность множества натуральных

чисел от a до b, включительно.

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

Входные данные содержат три строки. Первая строка содержит натуральное число a,

вторая строка содержит натуральное число b, третья строка содержит целое неотрицательное

число k (1 ≤ a ≤ b ≤ 10¹⁸, 0 ≤ k ≤ 10¹⁸).

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

Выходные данные должны содержать одно целое число: искомую k-плотность

множества натуральных чисел от a до b, включительно.

Ввод	Вывод
1 30 2	3

Арифметические алгоритмы (Теория чисел)Вещественные числа Линейный поиск

✓ 6✗ 661 100средняяВойти и решать

Домашнее задание#33080

Маленькому Арсению на кружке по системам счисления задали следующую задачу: перевести число X в системе счисления s1 в систему счисления s2. Недолго думая, он позвал на помощь своего лучшего друга Добрыню, который славился тем, что замечательно умел считать до 10 на пальцах. После нескольких бессонных ночей ребята общими усилиями справились с задачей.

Однако, на следующем занятии Арсению задали похожую задачу, где X, к сожалению, превышало 10. Тогда ребята решили обратиться в Летнюю Компьютерную Школу с просьбой написать универсальную программу, которая решает задачу для любых X, s1 и s2. Ваша цель – выполнить просьбу Арсения и Добрыни.

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

Во входных данных вашей программе дается 3 числа: исходное число X, основания систем счисления s1 и s2 (\(2 <= s1,\ s2 <= 10\)). Число X в десятичной системе счисления не превышает \(2 \cdot 10^9\).

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

В выходных данных должно находиться одно число, равное числу X в системе счисления s2, или -1, если входные данные некорректны.

Примеры

№	Входные данные	Выходные данные
1	101 2 10	5
2	200 2 10	-1

Разные системы счисления

✓ 48✗ 146800средняяВойти и решать

Следующее число#32965

Дано натуральное число N. Необходимо определить следующее за ним число, в двоичном разложении которого столько же единиц, сколько в двоичном разложении числа N.

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

Входные данные содержит одно натуральное число N (\(N <= 2^{30}\)).

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

Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	1	2
2	2	4
3	3	5

Двоичная система счисления

✓ 108✗ 1 012800средняяВойти и решать

Степень числа#32949

Для заданного натурального A найти минимальное натуральное N такое, что N в степени N (N, умноженное на себя N раз) делится на A.

Входные данные
На вход подается единственное число A (\(1 <= A <= 10^9\)).

Выходные данные
Необходимо вывести единственное число N.

Примеры

№	Входные данные	Выходные данные
1	8	4
2	13	13

Простые числа и разложение на множители

✓ 139✗ 1 086800средняяВойти и решать

Подпоследовательность#31927

Напишите программу, которая в некоторой последовательности целых чисел находит подпоследовательность наименьшей длины, сумма элементов в которой является числом, оканчивающимся на 6 или более нулей (делится без остатка на 1000000).

Первая строка ввода содержит одно целое число N (2 ≤ N ≤ 100000). Вторая строка ввода содержит N целых чисел в диапазоне от 1 до 10⁹, разделенных пробелами.

Вывести два целых числа – количество элементов в подпоследовательности и номер её первого элемента. Если существует несколько вариантов такой подпоследовательности с наименьшей длиной, выведите подпоследовательность с наименьшим номером первого элемента. Если такой подпоследовательности не существует – выведите одно число –1.

Ввод	Вывод
6 1 2 701000 299000 1000 999000	2 3
3 1 2 3	-1

Остатки

✓ 10✗ 671 000средняяВойти и решать

31922#31922

Даны два простых числа p и q. Надо расшифровать сообщение состоящее из последовательности чисел оканчивающееся нулем с помощью алгоритма RSA.

Входные данные
В первой строке вводятся p и q (3<=p,q<10), далее вводится длина N (N<10) и сообщение состоящее из натральных чисел не превышающее 10.

Ввод	Вывод
3 7 1 11 12 16 17 6 7 8 18 0 0	1234567890

Арифметические алгоритмы (Теория чисел)МЦКО-10. RSA

✓ 0✗ 121 400средняяВойти и решать

RSA. Расшифровать сообщение#31921

Даны два простых числа p и q. Надо расшифровать сообщение состоящее из последовательности чисел оканчивающееся нулем с помощью алгоритма RSA.

Входные данные
В первой строке вводятся p и q (3<=p,q<10) и сообщение состоящее из натуральных чисел оканчивающееся нулем.

Ввод	Вывод
3 7 1 11 12 16 17 0	1 2 3 4 5

Арифметические алгоритмы (Теория чисел)МЦКО-10. RSA

✓ 0✗ 251 300средняяВойти и решать

RSA. Зашифровать большое числовое сообщение#31920

Даны два простых числа p и q. Надо зашифровать сообщение длинной N с помощью алгоритма RSA.

Входные данные
В первой строке вводятся p и q (3<=p,q<100), далее вводится сообщение состоящее из цифр.

Ввод	Вывод
3 7 12345678901234567890	1 11 12 16 17 6 7 8 18 0 1 11 12 16 17 6 7 8 18 0

"Длинная" арифметика МЦКО-10. RSA

✓ 0✗ 271 300средняяВойти и решать

RSA. Зашифровать числовое сообщение#31919

Даный два простых числа p и q. Надо зашифровать сообщение длинной N с помощью алгоритма RSA.

Входные данные
В первой строке вводятся p и q (3<=p,q<10), далее вводится натуральное число, которое надо зашифровать, не превышающее 10⁹.

Ввод	Вывод
3 7 123456789	1 11 12 16 17 6 7 8 18

Быстрое возведение в степень МЦКО-10. RSA

✓ 8✗ 25900средняяВойти и решать

Расширенный алгоритм Евклида#31903

Даны натуральные числа \(a, b, c.\) Если уравнение \(a \cdot x + b \cdot y = c\) имеет решения в целых числах, то выведите через пробел \(НОД(a,b)\), \(x\) и \(y\) (какое-нибудь решение). Если решения не существует, то выведите слово Impossible.

Входные данные
Натуральные числа и не превышают по модулю 10000.

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	1 2 3	1 1 1
2	10 6 8	2 2 -2

Расширенный алгоритм Евклида

✓ 402✗ 990600лёгкаяВойти и решать

Быстрое возведение в степень#31901

Возводить в степень можно гораздо быстрее, чем за n умножений! Для этого нужно воспользоваться следующими рекуррентными соотношениями:

\(a^n=(a^2)^{n/2}\) при четном n,
\(a^n=a \cdot a^{n-1}\) при нечетном n.

Реализуйте алгоритм быстрого возведения в степень. Если вы все сделаете правильно, то сложность вашего алгоритма будет O(logn) .

Входные данные
Вводится вещественное число a и целое число n.

Выходные данные
Выведите ответ на задачу, с точностью 6 знаков после запятой.

Нельзя использовать стандартное возведение в степень.

Примеры

№	Входные данные	Выходные данные
1	2 7	128
2	1.00001 100000	2.71827

Быстрое возведение в степень

✓ 371✗ 1 140600лёгкаяВойти и решать

Кролик Клевер#31884

Кролик Клевер очень любит яблоки. Также он любит угощать яблоками своих друзей. У Кролика N друзей. Он собрал в саду K яблок и хочет их поделить поровну между своими друзьями, неделящийся остаток он оставит в корзинке. Сколько яблок достанется каждому другу и сколько яблок у него останется в корзине?
Помогите Кролику Клеверу посчитать эту информацию. Напишите для него программу.

Формат входных данных
Программа получает на вход два числа: N - количество друзей у кролика (не более 1000), K - количество яблок (не более 1000000). Каждое число записано в отдельной строке.

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

Линейные алгоритмы Остатки

✓ 7 606✗ 7 417200лёгкаяВойти и решать

Возведение a в степень b по модулю c#31881

Зная a, b, c (целые неотрицательные числа, не превосходят \(2\cdot10^9\)). Вычислите a в степени b по модулю c (\(a^b mod \ c\)).

Входные данные
На вход подаются три целых неотрицательных числа, разделенных одним пробелом.

Выходные данные
Выведите на экран ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	2 10 1000	24

Быстрое возведение в степень

✓ 348✗ 843600лёгкаяВойти и решать

Сложить две дроби#31872

Даны две рациональные дроби: \(a \over b\) и \(c \over d\). Сложите их и результат представьте в виде несократимой дроби \(m \over n\).

Входные данные
Программа получает на вход 4 натуральных числа a, b, c, d, не превосходящих 100.

Выходные данные
Программа должна вывести 2 натуральных числа m и n такие, что \({m \over n} = {a \over b}+ {c \over d}\) и дробь \(m \over n\) – несократима.

Примеры

№	Входные данные	Выходные данные
1	1 3 1 2	5 6

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

✓ 1 118✗ 1 731400лёгкаяВойти и решать

Применение Малой Теоремы Ферма#31866

Дано число a и простое число p. Найти такое минимальное число x, что \((a * x) \% p = 1\).

Входные данные
На вход подаются два натуральное числа a, p (\(a,\ p <= 10^{18} \)).

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	2 5	3

Малая теорема Ферма

✓ 263✗ 1 128600лёгкаяВойти и решать

Сумма функции Эйлера#31850

Посчитать сумму функций Эйлера вида: \(\phi(1) + \phi(p) + \phi(p^2) + ... + \phi(p^\alpha)\), где \(p\) - простое число, \(\alpha\)- натуральное число.

Входные данные
В одной строке через пробел подаются два числа \(p\) и \(\alpha\) (\(p <=11, \alpha <=60 \)).

Выходные данные
Выведите ответ на задачу.

Пример

№	Входные данные	Выходные данные
1	2 2	4

Функция Эйлера

✓ 199✗ 389400лёгкаяВойти и решать

Несложная сортировка#30779

Пусть x – целое положительное число, а k – натуральное число от 1 до 10. Пусть s(x, k) равно сумме цифр числа x, представленного в системе счисления по основанию k.

Задано n чисел a₁, a₂, ..., a_n. Необходимо вычислить последовательность b_i по формуле \(b_i = s(a_i, k_1) \cdot s(a_i, k_2)\). После этого отсортировать последовательность b_i по неубыванию.

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

Первая строка содержит три целых числа: n, k₁, k₂ (\(1 <= n <= 1000\), \(2 <= k_1, k_2 <= 10\)). Вторая строка содержит n целых чисел: a_i (\(1 <= a_i <= 10^9\)).

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

В ответе выведите n чисел – b_i в требуемом порядке.

Примеры

№	Входные данные	Выходные данные
1	9 10 10 1 2 3 4 5 6 7 9 8	1 4 9 16 25 36 49 64 81
2	10 2 2 1 2 4 8 16 32 64 128 256 512	1 1 1 1 1 1 1 1 1 1

Разные системы счисления

✓ 140✗ 94600лёгкаяВойти и решать