Условие задачи | | Прогресс |
Темы:
Быстрое возведение в степень
Зная a , b , c (целые неотрицательные числа, не превосходят \(2\cdot10^9\) ). Вычислите a в степени b по модулю c (\(a^b mod \ c\)).
Входные данные
На вход три целых неотрицаиельных числа, разделенных одним пробелом.
Выходные данные
Выведите на экран ответ на задачу.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
2 10 1000 |
24 |
| |
|
Темы:
Быстрое возведение в степень
Возводить в степень можно гораздо быстрее, чем за 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 |
| |
|
Темы:
Вывод формулы
Быстрое возведение в степень
Перестановки
N коров (1 ≤ N ≤ 105) Фермера Джона стоят в ряд. i-ая корова слева имеет метку i (1 ≤ i ≤ N).
ФД дал коровам M пар целых чисел s (L1,R1)…(LM,RM), где 1 ≤ M ≤ 100. Затем он сказал коровам повторить ровно K (1 ≤ K ≤ 109) раз процесс из M шагов:
Для каждого i от 1 до M:
Последовательность коров на позициях Li…Ri слева реверсивно меняют свой порядок.
Выведите метки всех коров слева направо для каждого i, (1 ≤ i ≤ N) после завершения описанного процесса.
Входные данные
Первая строка содержит числа N, M, K. Для каждого 1 ≤ i ≤ M строка i+1 содержит Li и Ri, два целых числа в интервале 1…N, где Li<Ri.
Выходные данные
На i-ой строке вывода, выведите i-ый элемент массива после выполнения всех инструкций K раз.
Примеры
№ |
Входные данные |
Выходные данные |
Пояснение |
1 |
7 2 2
2 5
3 7
|
1
2
4
3
5
7
6
|
Изначально порядок коров слева направо такой [1,2,3,4,5,6,7]
После первого шага процесса порядок станет таким [1,5,4,3,2,6,7]
После второго шага процесса порядок станет таким [1,5,7,6,2,3,4].
Повторив оба шага ещё раз получим результат, приведенный в выводе. |
| |
|