Системы счисления(36 задач)
"Длинная" арифметика(58 задач)
Простые числа и разложение на множители(45 задач)
Остатки(21 задач)
Быстрое возведение в степень(3 задач)
Быстрое преобразование Фурье(3 задач)
Суперчислом называется число, являющееся суммой двух простых чисел из диапазона [2…\(B\)]. Требуется найти все суперчисла из заданного диапазона [\(A\)…\(B\)].
Во входном файле даны два числа \(A\) и \(B\) (2 ≤ \(A\) ≤ \(B\) ≤ 40000), определяющие диапазон [\(A\)…\(B\)].
В выходной файл вывести все найденные суперчисла из заданного диапазона в возрастающем порядке.
3 10
4 5 6 7 8 9 10
В Нумберляндии проблема: простое число \(p\) ревнует к другому простому числу \(q\). Оно думает, что в интервале от \(a\) до \(b\) включительно содержится больше чисел, которые делятся на большую степень \(q\) чем на степень \(p\). Помогите \(p\) справиться с сомнениями. Пусть \(a(n, x)\) – максимальное \(k\), такое, что \(n\) делится нацело на \(x^k\). Будем называть число \(n\) \(p\)-доминирующим над числом \(q\) если \(a(n, p) > a(n, q)\). Необходимо определить, сколько чисел из интервала от \(a\) до \(b\) включительно являются \(p\)-доминирующими над \(q\).
Первая строка содержит четыре целых числа \(a, b, p, q (1 ≤ a, b ≤ 10^{18}, 1 ≤ p, q ≤ 10^9)\). \(p ≠ q, p\) и \(q\) — простые.
Выведите одно число — сколько чисел из интервала от \(a\) до \(b\) включительно являются \(p\)-доминирующими над \(q\).
В примере числа 3, 9, 15 и 18 являются 3 доминирующими над 2.
1 20 3 2
4
В настольном теннисе в результате каждой подачи разыгрывается одно очко. Подача переходит от игрока к игроку каждые 5 подач, т.е. первые пять раз подает первый игрок, затем 5 раз — второй, затем снова первый и т.д.
Партия играется до тех пор, пока кто-нибудь из игроков не наберет 21 очко. Тот, кто набрал 21 очко, признается победителем, и игра заканчивается.
Вася и Петя играли в игру, и забыли, кто должен подавать в данный момент. Однако они помнят, что первую подачу делал Вася, и счет в настоящий момент a:b (a очков у Васи и b очков у Пети). Напишите программу, которая по данным a и b будет определять, чья подача или устанавливать, что игра закончена.
Вводятся два числа a и b. Числа соответствуют реальному счету, т.е. оба числа целые, от 0 до 21 и не равны 21 одновременно.
Выведите одно из четырех сообщений:
· Vasya serves — если сейчас должен подавать Вася
· Petya serves — если сейчас должен подавать Петя
· Vasya wins — если игра завершена и выиграл Вася
· Petya wins — если игра завершена и выиграл Петя
4 1
Petya serves
15 0
Petya serves
21 12
Vasya wins
Вася, решая задачи демо-версии ЕГЭ, дошел до задачи B5, которая звучит так.
«У исполнителя Калькулятор две команды:
· прибавь 3
· умножь на 4
Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, а выполняя вторую, умножает его на 4.»
Далее в задаче требовалось получить из числа 3 число 57 не более, чем за 6 команд. Однако Вася заинтересовался, как можно для произвольных чисел \(a\) и \(b\) построить программу наименьшей длины получения числа \(b\) из числа \(a\).
Напишите программу, которая по заданным числам \(a\) и \(b\) вычислит наименьшее количество команд Калькулятора, которое нужно, чтобы получить из \(a\) число \(b\).
Вводятся два натуральных числа, не превышающих 1000 — \(a\) и \(b\).
Выведите наименьшее число команд, которое нужно, чтобы получить из \(a\) число \(b\). Если число \(b\) получить нельзя, выведите –1 (минус 1).
3 57
5
43 57
-1
10 10
0
В марсианских сутках \(N\) часов. У марсиан Ятеп и Ашам есть часы со стрелками, которые работают почти так же, как земные – большая стрелка делает один оборот в час, а маленькая – один оборот в сутки. Ятеп и Ашам поссорились и решили не разговаривать, пока стрелки часов не совпадут. Определите точный момент времени, когда это случится.
Во входном файле задано число тестов \(K\) (0 ≤ \(K\)<\(10^4\)), далее для каждого теста указаны целые числа \(N\), \(A\), \(B\) и \(C\) (1<\(10^9\), 0 ≤ \(A\), 0 ≤ \(B\) < \(10^9\)). Числа \(A\), \(B\) и \(C\) означают, что Ятеп и Ашам поссорились в \(A\)+\(B\)/\(C\) часов.
Для каждого теста выведите искомое время в том же формате: числа \(A\), \(B\) и \(C\), такие, что искомое время равно \(A\)+\(B\)/\(C\) (0 ≤ \(A\), 0 ≤ \(B\), дробь \(B\)/\(C\) – несократимая).
2 12 11 0 1 12 0 0 1
0 0 1 1 1 11