GCD Queries

All submissions for this problem are available.
You are given an array $arr$ with $n$ integers. You are asked to execute a maximum of $q$ queries of the following kind: print the $GCD$ of the elements in the array located between indices $l$ and $r$ (oneindexed), both inclusive. However, you will not be given $l$ and $r$ for each query. Instead, you will be given 5 integers $l_0$, $r_0$, $k_0$, $k_1$ and $v_0$. For the first query, $l=l_0$, $r=r_0$. For subsequent queries, the indices $l$ and $r$ should be generated using the following code: ``` //l and r currently hold their respective values from the previous query if((ans^v0)%2==1) //ans is the output of the previous query l0=l+(ans^(l+r)^l)%k0; else l0=l; r0=r+(ans^(r+l)^r)%k1; if(l0==l and r0==r){ l0++; } ``` `if(l0`>`r0){` ``` swap(l0,r0); } l=l0; r=r0; ``` (The code is in C++; '^' denotes the XOR operator and '%' denotes the modulo operator) You must keep generating and answering queries until either the maximum number of queries $q$ is reached or the indices go out of bounds (specifically if $r>n$). Solve the queries quickly! ###Input:  The first line of the input contains two space separated integers $n$ and $q$ denoting the number of elements in $arr$ and the maximum number of queries respectively.  The second line of the input contains $n$ spaceseparated integers $arr_1, arr_2, ..., arr_n$ denoting the values of the elements of the array.  The third line contains 5 spaceseparated integers $l_0$, $r_0$, $k_0$, $k_1$ and $v_0$, where each of these integers are described in the problem statement above. ###Output: For each query, output in a single line an integer corresponding to the $GCD$ of the elements from index $l$ to index $r$. As mentioned earlier, you must keep answering queries either till $q$ queries are reached or till one of the indices goes out of bounds. ###Constraints  $1 \leq n \leq 10^6$  $1 \leq q \leq 10^6+10$  $1 \leq arr_i \leq 10^9$  $1 \leq l_0, r_0, k_0, k_1 \leq n$  $l_0 \leq r_0$  $1 \leq v_0 \leq 10^8$ ###Sample Input: 5 5 2 4 8 16 32 2 3 5 4 21 ###Sample Output: 4 32 ###Explanation: Initially, $l=2$ and $r=3$. Therefore, answer for the first query is $GCD(arr_2, arr_3) = GCD(4, 8) = 4$. After following the procedure to generate a new query, now $l=5$ and $r=5$. Therefore, answer for the second query is $arr_5 = 32$. For the next query, $l=7$ and $r=8$. We have gone outside the bounds of the array, so we stop answering queries.Author:  teja349 
Tags  teja349 
Date Added:  6042018 
Time Limit:  1 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, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions