| Problem description | | Progress |
|
Темы:
Fermat's Little Theorem
Given a number a and a prime number p. Find the minimum number x such that \((a * x) \% p = 1\).
Input
The input is two natural numbers a, p (\(a,\ p <= 10^ {18}
\)).
Imprint
Print the answer to the problem.
Examples
| |
![]()
|
|
Темы:
Prefix sums(minimums, ...)
Fermat's Little Theorem
Remains
Fast exponentiation
Fomin's gang consists of n groups, each of which has ai 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 ai (\(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 – li and ri (\(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 |
| |
![]()
|