Бинарное возведение в степень.
Пусть дано число a и его нужно возвести в степень n, воспользуемся тем свойством, что a^n = a^(n/2) * a^(n/2). Пусть n – четно, тогда для следующего шага выберем n/2 и перейдем к следующему n, вычисляя только одну из частей получившегося произведения и после этого, просто возведем эту часть в степень 2. Пусть n нечетно, тогда на данном шаге перейдем к степени n-1(как в обычно алгоритме возведения в степень).
Реализуем описанный алгоритм в виде функции. В качестве параметров принимаются два целых числа a и n, внутренняя переменная ans хранит в себе результат вычислений.
int bin_pow(int a, int n)
{
int ans = 1;
while(n)
{
if(!n%2)
{
a *= a;
n /= 2;
}
else
{
ans *= a;
n--;
}
}
return ans;
}
Задачи(простая математика и теория чисел).
codeforces.ru:
http://codeforces.ru/problemset/problem/4/A
Арбуз
ограничение по времени на тест
1 second
ограничение по памяти на тест
64 megabytes
ввод
standard input
вывод
standard output
В один из жарких летних дней Петя и его друг Вася решили купить арбуз. Они выбрали самый большой и самый спелый, на их взгляд. После недолгой процедуры взвешивания весы показали w килограмм. Поспешно прибежав домой, изнемогая от жажды, ребята начали делить приобретенную ягоду, однако перед ними встала нелегкая задача. Петя и Вася являются большими поклонниками четных чисел, поэтому хотят поделить арбуз так, чтобы доля каждого весила именно четное число килограмм, при этом не обязательно, чтобы доли были равными по величине. Ребята очень сильно устали и хотят скорее приступить к трапезе, поэтому Вы должны подсказать им, удастся ли поделить арбуз, учитывая их пожелание. Разумеется, каждому должен достаться кусок положительного веса.
Входные данные
В первой и единственной строке входных данных записано целое число w (1 ≤ w ≤ 100) — вес купленного ребятами арбуза.
Выходные данные
Выведите YES, если ребята смогут поделить арбуз на две части, каждая из которых весит четное число килограмм, и NO в противном случае.
Примеры тестов
Входные данные
8
Выходные данные
YES
Примечание
Например, ребята могут поделить арбуз на две части размерами 2 и 6 килограммов соответственно (другой вариант — две части 4 и 4 килограмма).
http://codeforces.ru/problemset/problem/82/A
A. Double Cola
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
standard input
вывод
standard output
Шелдон, Леонард, Пенни, Раджеш и Говард стоят в очереди к автомату по продаже баночек с напитком «Double Cola», других людей в очереди нет. Первый в очереди (Шелдон) покупает баночку, выпивает ее содержимое и раздваивается! Получившиеся два Шелдона встают в конец очереди. Затем следующий в очереди (Леонард) покупает баночку, выпивает и встает в конец очереди в двойном экземпляре, и так далее. Этот процесс продолжается до бесконечности.
Например, третью баночку колы выпьет Пенни, и очередь будет выглядеть так: Раджеш, Говард, Шелдон, Шелдон, Леонард, Леонард, Пенни, Пенни.
Напишите программу, которая выведет имя человека, выпившего n-ую баночку.
Обратите внимание, что в самом начале очередь выглядит так: Шелдон, Леонард, Пенни, Раджеш, Говард. Первым человеком является Шелдон.
Входные данные
Входные данные состоят из единственного целого числа n (1 ≤ n ≤ 109).
Гарантируется, что в претестах проверяется правильность написания всех пяти имен, то есть в них встречаются все пять возможных ответов.
Выходные данные
Выведите единственную строку — имя человека, который выпьет n-ую баночку колы. Баночки нумеруются от 1. Обратите внимание, что следует выводить имена в следующем написании: "Sheldon", "Leonard", "Penny", "Rajesh", "Howard" (без кавычек). Именно в этом порядке друзья стоят в очереди изначально.
Примеры тестов
Входные данные
1
Выходные данные
Sheldon
Входные данные
6
Выходные данные
Sheldon
Входные данные
1802
Выходные данные
Penny
3. http://codeforces.ru/problemset/problem/50/A
A. Укладка доминошками
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
standard input
вывод
standard output
Дана прямоугольная клеточная доска размера M × N клеток. Также дано неограниченное количество стандартных доминошек размера 2 × 1 клетку. Доминошки можно поворачивать. Требуется уложить как можно больше доминошек на доску так, чтобы соблюдались следующие условия:
1. Каждая доминошка полностью покрывает две клетки доски.
2. Никакие две доминошки не перекрываются.
3. Каждая доминошка полностью лежит внутри доски. Касание краев доски допускается.
Найдите максимальное количество доминошек, которое можно уложить с данными ограничениями.
Входные данные
В единственной строке записано два целых числа M и N — размеры доски в клетках (1 ≤ M ≤ N ≤ 16).
Выходные данные
Выведите одно число — максимальное количество доминошек, которое можно уложить.
Примеры тестов
Входные данные
2 4
Выходные данные
4
Входные данные
3 3
Выходные данные
4
4. http://codeforces.ru/problemset/problem/124/A
A. Количество позиций
ограничение по времени на тест
0.5 second
ограничение по памяти на тест
256 megabytes
ввод
standard input
вывод
standard output
Петя стоит в шеренге из n человек, но точно не знает на какой позиции. Он может сказать, что перед ним стоит не менее a человек, а после него — не более b человек. Найдите количество позиций, на которых может стоять Петя.
Входные данные
В единственной строке записано три целых числа n, a и b (0 ≤ a, b < n ≤ 100).
Выходные данные
Выведите одно число — количество искомых позиций.
Примеры тестов
Входные данные
3 1 1
Выходные данные
2
Входные данные
5 2 3
Выходные данные
3
Примечание
В первом примере возможные позиции: 2 и 3 (если нумеровать позиции с 1).
Во втором примере: 3, 4 и 5.
5. http://codeforces.ru/problemset/problem/80/A
A. Предсказание Панорамикса
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
standard input
вывод
standard output
Простым числом называется число, которое имеет ровно два различных делителя: единицу и само себя. Например, числа 2, 7, 3 являются простыми, а 1, 6, 4 — нет.
Следующим после x простым числом называется наименьшее простое число, большее x. Например, после 2 следующим простым является 3, а после 3 следующим простым является 5. Учтите, что для каждого числа есть ровно одно следующее простое. То есть 5 не является следующим простым для 2.
Однажды, холодным апрельским утром Панорамикс предсказал, что скоро освободится Какофоникс из своей смирительной рубашки, и чёрный день наступит для жителей галльской деревни.
Этот день, после третьей порции волшебного снадобья, определился друидом очень просто: если в некоторый день Астерикс и Обеликс побьют ровно x римских солдат, где x — простое число, а на следующий день они побьют ровно y римских солдат, где y — следующее после x простое число, то стоит ждать конца света, ибо ничто не сможет сдержать Какофоникса с его адской песней.
Вчера галлы побили n римских солдат и оказалось, что число n — простое! Сегодня их жертвами стал отряд из m римлян (m > n). Определите, стоит ли ждать чёрного дня после сегодняшней победы Астерикса и Обеликса?
Входные данные
В первой и единственной строке входного потока дано два натуральных числа — n и m (2 ≤ n < m ≤ 50). Гарантируется, что число n — простое.
В претестах рассмотрены все случаи с ограничениями 2 ≤ n < m ≤ 4.
Выходные данные
Выведите YES, если число m оказалось следующим простым после n, или NO в противном случае.
Примеры тестов
Входные данные
3 5
Выходные данные
YES
Входные данные
7 11
Выходные данные
YES
Входные данные
7 9
Выходные данные
NO
6. http://codeforces.ru/problemset/problem/26/A
A. Почти простые числа
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
standard input
вывод
standard output
Число называется почти простым, если оно имеет ровно два различных простых делителя. Например, числа 6, 18, 24 являются почти простыми, а 4, 8, 9, 42 — не являются. Найдите количество почти простых чисел от 1 до n включительно.
Входные данные
В первой строке входного файла записано число n (1 ≤ n ≤ 3000).
Выходные данные
Выведите количество почти простых чисел от 1 до n включительно.
Примеры тестов
Входные данные
10
Выходные данные
2
Входные данные
21
Выходные данные
8
7. http://codeforces.ru/problemset/problem/17/A
A. Проблема Нольдбаха
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
64 megabytes
ввод
standard input
вывод
standard output
Никита интересовался простыми числами, и однажды прочитал о проблеме Гольдбаха. Она гласит, что любое четное число большее 2 можно представить в виде суммы двух простых чисел. Никита заинтересовался этим и решил придумать себе на голову проблему, и назвал он её проблемой Нольдбаха. Так как он интересовался исключительно простыми числами, проблема Нольдбаха гласила, что по крайней мере k простых чисел от 2 до n включительно представимо в виде суммы трех чисел: двух соседних простых чисел и 1. Например, 19 = 7 + 11 + 1, или 13 = 5 + 7 + 1.
Два простых числа называются соседними, если между ними не существует других простых чисел.
Вам предстоит помочь Никите, и сказать, прав он или ошибается.
Входные данные
В первой и единственной строке входных данных содержится два целых числа n (2 ≤ n ≤ 1000) и k (0 ≤ k ≤ 1000).
Выходные данные
В единственной строке выходных данных выведите слово YES, если не менее k простых чисел в промежутке от 2 до n представимы в виде описанном выше. В противном случае, выведите слово NO.
Примеры тестов
Входные данные
27 2
Выходные данные
YES
Входные данные
45 7
Выходные данные
NO
Примечание
В первом примере ответ YES, так как чисел, которые можно представить в описанном виде не меньше двух (например, 13 и 19). Во втором примере ответ NO так как нельзя представить в искомом виде 7 простых чисел от 2 до 45.