Explain the solution to the problem(in c/c++) CodeChef: Practical coding for everyone
1 Like
most of athe AC submissions are in pythonâŚ
the logic common il all those submissions,
n=n*(x-1)
y=pow(x,m+1,n)-1
y=(y+n)%n
print y/(x-1)
but cant figure out how this could give the result of the series 1+X+X^2+âŚ+X^m (mod n)âŚ
(1+x+x^2+âŚx^m )(mod n) = ((x^(m+1)-1)/(x-1))(mod n)
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.
13 Likes
Few ideas:
Slightly Slow Solution
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 we need to calculate x^m extra.
For calculating (x * y) % mod, if we use log n steps, then overall time complexity of above recursive way would be T(n) = T(n / 2) + log^2n = log^3n which wonât pass. So calculate (x * y) % mod faster by a trick which you ca find on the internet (basically storing the data in long double and avoiding overflow).
#Jury solution
Group 1 + x + x^2 + ⌠x^m
as (1 + x) ( 1 + x^2 + ⌠)
Now it can be done in log^2(n) steps only.
1 Like
how would you do this in c++. n*(x-1) canât be stored in long long
1+X+X^2+âŚ+X^m (mod n)=((x^m+1)-1)/(x-1).Hope now you can understand!
1 Like
To solve it in c++ either you can use bigint library (see my solution : CodeChef: Practical coding for everyone) or else you can do the multiplication in double and then take the required number with modulus (see this solution: CodeChef: Practical coding for everyone)
1 Like
yea i solved it using bigint tooâŚbut i thought there was some better approach that doesnât need it âŚ
hmm⌠as n*(x-1) would overflow the long long, we need to use big-integers, or apply other tricks. I donât know why my solution using big-int(I have been using this big-int implementation for over a year and gives ac on other questions) was producing wrong answer while changing to python gave ac: can anyone point out some mistake: CodeChef: Practical coding for everyone
@dpraveen I got wa on using the long double hack 
finally I had to find other method of multiplying numbers so i guess the long double wont work
bigint pres = fres%n;
if(pres<0) pres+=n;
Firstly you donât need these, when you divide by x-1, thatâs your required answer. Secondly, this would screw up your answer since the â%â operator is defined for int and bigint , not for long long. So fres%n, would call the âintâ one, and return an int, that would obviously be wrong.
1 Like
@fauzdar65: thanks for the enlightenment, I wasted 30 minutes in the middle of the contest, making brute force program, generating random inputs(not large enough) and checking output to see if something is wrong, but could not get it, only to leave it and re-code it in python 2 hours later.