Problem link : contest
Difficulty : Medium
Pre-requisites : recursion, repeated squaring
Explantion of Amit Saharana
As 1 + x + x^2 + x^3 + … . + x^m = (x^m - 1) / (x - 1).
Now, we can’t directly divide first by calculating numerator modulo n. Also, inverse of x-1 modulo n can’t be calculated as it is not given that gcd(x-1,n)=1. Hence we just take a newmod=n(x-1). calculate numerator modulo newmod and then divide by (x-1) to get final result.
This is similar to the problem of dividing by 30 in FLOORI4 question of September Long Challenge, 2014.
Why this is correct: Suppose you have to calculate (a/b) mod c and you encounter similar problem because a is too large directly, and gcd(b,c)!=1.
Let (a/b) mod c = y then (a/b) = xc+y (for some x)
=> a = xcb + yb => a = x(bc) + yb => a (mod (bc)) = yb so to calculate y, you can calculate a mod bc to get yb and divide by b to get y.
In the above problem, a = x^(m+1)-1, b = x-1, c = n.
Note that (x - 1) * n won’t fit in long long. So for this, you should use either use manually written big integer library or use BigInteger library in Java. Many people also used python for precisely this reason.
To find 1 + x + x^2 + … + x^m.
Assume m is even, group the expression like this
1 + x^2 + … + x^m + x + x^3 + x^5 + x^(m - 1)
= 1 + x^2 + … + x^m + x (1 + x^2 + x^4 + x^(m - 2))
So you can notice that we can write a recursive function. Note that in the two expressions, first expression has x^m extra.
So we need to calculate x^m extra. For that we use the normal repeated squaring idea.
For calculating (x * y) % mod, if we use log n steps (repeated squaring idea, see tester’s code), then overall time complexity of above recursive way could be
found by following equation
T(n) = T(n / 2) + log^2n = log^3n which won’t pass.
So calculate (x * y) % mod faster by a trick which you can find on the internet (basically storing the data in long double and avoiding overflow). I will
add the link soon.
This time instead of using normal grouping, we do different grouping.
Group two consecutive terms together.
Write 1 + x + x^2 + … x^m (Assume m is even).
= (1 + x) + (x^2 + x^3) + (x^4 + x^5) + … + (x^(m - 1) + x^m).
as (1 + x) ( 1 + x^2 + … )
Now your recurrence relation for time complexity will be T(n) = T(n / 2) + O(log n).
So this will take log^2(n) steps only. See tester’s code for more details.
Tester’s solution: link