Problem link:##
Setter: Aman Kumar Singh
Tester: Indrajit Sinha.
Difficulty:##
Easy
Prerequisites:##
Modular division Properties
Explanation:##
As the N is 10^18 so we cannot form any type of array upto N.And as q is also very large 10^5
each query has to be answered in O(1) time complexity.For each query there are two numbers
l and r and the answer to the query is the sum of all the numbers from i’th number of the
sequence to the r’th number of sequence[l,r]. First we find the middle position of of the
sequence.Then there can be 3 consequences:
-
l and r both are on the right of middle point.
-
l and r both are on the left of middle point.
-
l is on the left of the middle point and r is on the left of the middle point.
Let MOD_VAL=10^9+7
For 1 and 2 we just find the number which is corresponding to the l th position from middle
and the number which is corresponding to the r th position from middle. And we just use the
formula
((Number of terms in the AP)% MOD_VAL*(First term + last term) %
MOD_VAL*(2^(MOD_VAL-2))%MOD_VAL)%MOD_VAL (where 2^(MOD_VAL-2))%MOD_VAL is
the multiplicative mod inverse of 2).
For 3rd consequence there will be 2 AP one on the right of middle and one on left of middle,
we find the number which is corresponding to the l th position from middle and the number
which is corresponding to the r th position from middle. And we just use the formula
((Number of terms in the AP)% MOD_VAL*(First term + middle term) %
MOD_VAL*(2^(MOD_VAL-2))%MOD_VAL)%MOD_VAL (where 2^(MOD_VAL-2))%MOD_VAL is
the multiplicative mod inverse of 2)+
((Number of terms in the AP)% MOD_VAL*(2 + last term) % MOD_VAL*(2^(MOD_VAL2))%MOD_VAL)%MOD_VAL
(where 2^(MOD_VAL-2))%MOD_VAL is the multiplicative mod
inverse of 2)
Time Complexity:##
O(1) per query
Author’s and Tester’s Solution:##
Author’s solution is here
Tester’s solution is here