CNTSOLS - Editorial

editorial
, , , , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

PREREQUISITES

Simple Math, Repeated Squaring

PROBLEM

You are given three integers d, m and N in the following relation

xd + yd + zd ≡ m, modulo N

Find the number of solutions of the above equation where

0 ≤ x, y, z ≤ U

EXPLANATION

The first observation to be made is that the value of N is very small. We already know that

ab = (a % N)b, modulo N

Despite the fact that U is a large number, it is only relevant for us to find the solutions (X, Y, Z) which satisfy

0 ≤ X, Y, Z < N

and for each solution (X, Y, Z), calculate the number of values in the range

0 ≤ x, y, z ≤ U

such that

  • x = X, modulo N
  • y = Y, modulo N
  • z = Z, modulo N

Let us say that

  • A[t] = td % N
  • 0 ≤ t < N

Now, we can iterate through the list of unique solutions (X, Y, Z)

for X = 0 to N-1
	for Y = 0 to N-1
		for Z = 0 to N-1
			if (A[X] + A[Y] + A[Z]) % N = m
				process(X, Y, Z)

The complexity of calculating A[] is O(N log d) if we use repeated squaring.

In the worst case, the number of times process() is called is O(N3).

For each solution (X, Y, Z) we wish add the solutions (x, y, z) from the complete range. The number of values of x, satisfying

  • x = X, modulo N
  • 0 ≤ x ≤ U

is

number-of-sols(X) =

floor(U / N) + {
	1, if (U % N > 0 AND X ≤ U % N),
	0, otherwise
}

Now, the number of solutions (x, y, z) for (X, Y, Z) is simply

answer = 0

process(X, Y, Z) =
	answer = answer +
		number-of-sols(X) *
		number-of-sols(Y) *
		number-of-sols(Z)

Thus, the answer can be found in O(N3) time.

CODING COMMENTARY

The answer has to be found modulo 109</sup+7. This leaves a lot of scope for integer overflow. Make sure that your implementation uses 64-bit integers for all intermediate results, at the least.

64-bit integers can handle the overflow of multiplying two 32-bit integers, but not three. You must find the modular result after each product.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

11 Likes
2

Ah! My solution, just like the editorial!

3

Well I was using a similar concept for my first solution but i got WA. Please tell me what is wrong with this approach.
code: http://www.codechef.com/viewsolution/2510118

4

I also used the nested loop procedure. But instead on looping on x,y and z, I looped on i,j,k such that
xd ≡ i(mod n),
yd ≡ j (mod n),
zd ≡ k(mod n).
I pre-computed number of solutions of x for xd ≡ i(mod n) for each 0<= i< n.

for i = 0 to N-1  
    for j = 0 to N-1  
        for k = 0 to N-1  
            if (i+j+k) % N == m  
                count+= solution[i]*solutions[j]*solutions[k];

I was getting wrong answer while submitting but I tested many large cases as well as border cases. All were matching with output of an accepted solution.

Is above procedure wrong, or there is any particular test case which fails in this algorithm?

1 Like
5

How does the condition (i+j+k) % N == m mean that xd ≡ i(mod n), and so on?

6

I also did like you. See this solution as reference http://www.codechef.com/viewsolution/2464513

7

maybe your pow function has a bug when modulo = 1 . it was my bug , hope this helps.

8

What part of this solution is DP ?

1 Like
9

I had not tagged the problem as Dynamic Programming. Have removed it from the PREREQUISITES as well.

10

This problem can be done using DP in O(n^2) time.

11

Why not X will always be less then U%N in number-of-sols?

12

the trick behind upperlimit of N is really good and was not easy to find out…