Chef and Functions
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef has just been introduced to functions and he has been experimenting a lot with the different kinds of functions. In the process, the chef has come up with an interesting problem for you.
Chef defines a function root(i, x) which gives the greatest integer less than or equal to the i th root of a positive integer x . For example, root(2, 4) is 2 and root(2, 2) is 1 .
Now the chef defines another function val(x, A, N) as follows :
val(x, A, N) = root(1, x)*A + root(2, x)*A + ... + root(N, x)*A[N]
where A is an array of integers of size N (indexed from 1 onwards) and x is a positive integer.
You are given the array A and its size N . You need to find out the value of val(x, A, N) for several values of x . Since this number can be very large, print the result modulo 109 + 7 .
The first line contains an integer T denoting the number of test cases. Each test case begins with a line containing two integers N and Q denoting the size of array A and the number of queries. The second line of each test case consists of N space separated integers where the ith integer represents A[i]. The third line of each test case consists of Q space separated integers denoting the value of x for the ith query.
For each test case, print in a single line Q integers, where the ith integer represents the answer to the ith query. ( i.e val(x, A, N) % ( 109 + 7 ) )
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 104
- 1 ≤ Q ≤ 15000
- -109 ≤ A[i] ≤ 109
- 1 ≤ x ≤ 1018 for each number in the query.
Input: 1 3 2 4 5 6 8 30
Output: 54 163
(root(1,8)*4 + root(2,8)*5 + root(3,8)*6) % 1000000007 = (8*4 + 2*5 + 2*6) % 1000000007 = 54 % 1000000007 = 54
(root(1,30)*4 + root(2,30)*5 + root(3,30)*6) % 1000000007 = (30*4 + 5*5 + 3*6) % 1000000007 = 163 % 1000000007 = 163
|Tags||binary-search, june14, medium, number-theory, viv001|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.