Product on the segment by modulo
All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Given an array A of N integers and an integer P ( not necessarily prime ). You are required to answer Q queries, i-th query is described by two numbers Li, Ri, the answer to the query is the product of all numbers in array A from index Li to index Ri modulo P. You have to answer the queries in online mode, that is you can't know a query before you answer all queries that are before it.
the first line contains one integer T , the number of test-cases.
the first line of each test-case contains N, P, Q .
the third line contains N space-separated integers, the of elements array A .
the fourth line contains array B which consists of floor(Q/64) + 2 integers . Let's number the queries starting from 0. If i is divisible by 64 then:
Li = (Bi / 64 + x) mod N, Ri = (Bi / 64 + 1 + x) mod n .
Otherwise: Li = (Li-1 + x) mod N, Ri = (Ri-1 + x) mod N . If Li > Ri you should swap them. here x is equal to 0 if it's the first query, otherwise it's equal to the answer of the previous query plus 1 modulo P.
After each test-case you have to print one number - the value of x after the the last query modulo P
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 106
- 1 ≤ Q ≤ 2 * 107
- 2 ≤ P ≤ 109
- 0 ≤ A i ≤ 109
- 0 ≤ B i ≤ n - 1
- The sum of N over all testcases does not exceed 106 and sum of Q over all testcases does not exceed 2 * 107
- Subtask 1 (20 points) : P is prime and all numbers of A in range [1; P - 1]
- Subtask 1 (20 points) : P = xk where x is prime and k is integer and all numbers of A in range [1; P - 1]
- Subtask 3 (60 points) : Original constraints
Input: 2 6 113 3 1 2 3 4 5 6 1 4 6 113 70 1 2 3 4 5 6 1 4 3 Output: 8 21
|Tags||altruist_, medium-hard, nov17|
|Time Limit:||4 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.