CNTSOLS - Editorial






Simple Math, Repeated Squaring


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


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


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

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


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.


Can be found here.


Can be found here.


Ah! My solution, just like the editorial!

Well I was using a similar concept for my first solution but i got WA. Please tell me what is wrong with this approach.

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

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

I also did like you. See this solution as reference

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

What part of this solution is DP ?

1 Like

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

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

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

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