Explain the solution to the problem IITK1P07 in WPC1401

general
, ,
1

Explain the solution to the problem(in c/c++) http://www.codechef.com/WPC1401/problems/IITK1P07

1 Like
2

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)…

3

(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
4

how would you do this in c++. n*(x-1) can’t be stored in long long

5

1+X+X^2+…+X^m (mod n)=((x^m+1)-1)/(x-1).Hope now you can understand!

1 Like
6

To solve it in c++ either you can use bigint library (see my solution : http://www.codechef.com/viewsolution/4936928) or else you can do the multiplication in double and then take the required number with modulus (see this solution: http://www.codechef.com/viewsolution/4937415)

1 Like
7

yea i solved it using bigint too…but i thought there was some better approach that doesn’t need it …

8

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: http://www.codechef.com/viewsolution/4932832

9

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
10

@dpraveen I got wa on using the long double hack :frowning: finally I had to find other method of multiplying numbers so i guess the long double wont work

11

@dpraveen : I got the grouping part but how do we use it and avoid overflows too?

12

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
13

@chalubhalu +1 for using “pow_bhaji” for fast exponentiation :smiley:

14

@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.