Hello everybody,

Today was the second day of RMI(Romanian master of informatics) and I participated onsite. It took me a couple of hours to solve two of the problems and then I had whole three to tackle the last one. Alas, it turned out to be too difficult for me to get more than 10-20 points.

The short statement of the problem is simply :

Support 2 types of queries on an array of size N:

1) Given "L R" find greatest common divisor of all numbers from index L to R, that is gcd(a[L], a[L+1],..., a[R])

2) Given "L R k" update the array in the following way:

a[L]+=k

a[L+1]+=2*k

...

a[R]+=(R-L+1)*k

There are up to 100,000 numbers and queries with time limit of 1s and memory limit of 128MB. The initial numbers are up to 200,000,000 and in each query of type 2 we can have k up to 200,000,000 (resulting in numbers becoming as big as 10^18).

Query problems are usually my favourite but I couldn't come up with anything here. The queries just seem very different. If someone has some solution, please share.