Fast exponentiation

Plus

Problem description Progress

ID 31881. Raising a to the power of b modulo c

Knowing a, b, c (non-negative integers, do not exceed \(2\cdot10^ 9\)). Evaluate a to the power of b modulo c (\(a^b mod \ c\)).

Input
The input is three non-negative integers separated by one space.

Imprint
Display the answer to the problem.

Examples

#	Input	Output
1	2 10 1000	24

ID 31901. Fast exponentiation

Темы: Fast exponentiation

Raising to a power is much faster than n multiplications! To do this, use the following recurrence relations:

\(a^n=(a^2)^{n/2}\) even n,
\(a^n=a \cdot a^{n-1}\) for odd n.

Implement the fast exponentiation algorithm. If you do everything right, then the complexity of your algorithm will be O(logn) .

Input
Enter a real number a and an integer n.

Imprint
Print the answer to the problem, with an accuracy of 6 decimal places.

You can't use standard exponentiation.

Examples

#	Input	Output
1	2 7	128
2	1.00001 100000	2.71827

ID 39514. One-two-three-four-five cow change

Темы: Formula derivation Fast exponentiation Permutations

N cows (1 ≤ N ≤ 10⁵) Farmer John stand in a row. The i-th cow on the left has label i (1 ≤ i ≤ N).
FD gave the cows M pairs of integers s (L₁,R₁)…(L_M,R_M), where 1 ≤ M≤ 100. Then he told the cows to repeat exactly K (1 ≤ K ≤ 10⁹) times the process of M steps:

For every i from 1 to M:
The sequence of cows in positions Li…Ri on the left reverses their order.
Print the labels of all cows from left to right for each i, (1 ≤ i ≤ N) after the process is completed.

Input
The first line contains the numbers N, M, K. For each 1 ≤ i≤ M string i+1 contains L_i and R_i, two integers in the interval 1…N, where L_i<R_i.

Imprint
On the i-th line of the output, print the i-th element of the array after executing all instructions K times.

Examples

#	Input	Output	Explanation
1	7 2 2 25 3 7	1 2 4 3 5 7 6	Initially, the order of cows from left to right is [1,2,3,4,5,6,7] After the first step of the process, the order will be [1,5,4,3,2,6,7] After the second step of the process, the order will become [1,5,7,6,2,3,4]. Repeating both steps one more time we get the result shown in the output.

ID 30699. Gangs of Fomin No. 2

Темы: Prefix sums(minimums, ...) Fermat's Little Theorem Remains Fast exponentiation

Fomin's gang consists of n groups, each of which has a_i people. q raids are planned. The i-th raid will include exactly one robber from each group whose number lies in the segment \([l_i, r_i]\).

Melekhov is sad, so for each raid he decided to calculate the number of possible units modulo \(10^9 + 7\). However, Gregory is constantly thinking about the meaning of life and searching for the truth, so he cannot concentrate on calculations and asks you for help.

Input
The first line contains the number n (\(1 <= n <= 10^5\)) – the number of groups in Fomin's gang.
The second line contains n natural numbers a_i (\(1 <= a_i < = 10^6\)) – the number of people in the i-th group.
The third line contains the number q – number of raids.
The following are q lines, each containing two numbers – l_i and r_i (\(1 <= l_i <= r_i <= n\)) – numbers of groups participating in i-th raid.

Imprint
Print q numbers, each on a separate line – response to the task.

Examples

#	Input	Output
1	6 1 3 7 1 4 100 3 1 3 34 26	21 7 8400