All submissions for this problem are available.
Abhishek loves to play with Fibonacci numbers. One day he came up with a problem. Given N pairs of numbers,he had to perform two types of operations. First type of operation was an update operation. In this operation, he was given three integers B ,P and Q. He had to replace the Bth pair (1 indexing) in the list with new pair of numbers P and Q. In the second type of operation, two integers L and R were provided. This time the task was to find the pair in the range L to R(both inclusive) with the maximum X value and to print the X value of that pair.
For a pair with values P and Q,
X = gcd(fib(P), fib(Q)) % M
Where fib(i) denotes the (ith Fibonacci) and M=109+7
Note : Consider 1 indexing and Fibonacci numbers starting with 1 i.e fib(1)=1,fib(2)=1,fib(2)=2,etc
Now, Abhishek has been given a list of operations to be performed.Help him to solve them correctly.
The first line contains a single integer N denoting the number of pairs.
Each of the next N lines contain a pair of integers P and Q .
The next line contains a single integer K denoting the number of operations to be done.
Each of the next K lines denote either update or maximum operation. For an operation to be an update operation, there must be 4 integers such that the first integer is 0 which denotes it is an update operation (type 0) . The next 3 integers B, P and Q as described above denote the Bth pair to be replaced with P and Q. For maximum operation, there are 3 integers. The first integer is 1 (type 1 for maximum operation) and the next two integers L and R denote the range for the particular operation.
Output answer of each operation of type 1(Maximum) separated by space.
0 2 6 8
1 1 3
1 2 3
Pair 1:(2, 3),Pair 2:(5,10),Pair 3:(12,8)
The first operation is an update operation.
Thus Pair 2 changes to(6,8).
The next operation is to find the pair in the range [1,3] with maximum X value.
X value for pair 1:gcd(fib(2),fib(3))%(109+7)=gcd(1,2)%(109+7)=1
X value for pair 2:gcd(fib(6),fib(8))%(109+7)=gcd(8,21)%(109+7)=1
X value for pair 3:gcd(fib(12),fib(8))%(109+7)=gcd(144,21)%(109+7)=3
Thus,the maximum value of X is 3.
The next operation is again a type(1)maximum operation in the range [2,3]
X value for pair 2:1
X value for pair 2:3
Thus, the maximum value of X is 3.
|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, 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, SCM chicken, CLOJ, FS|
Fetching successful submissions