PROBLEM LINKSDIFFICULTYEASY PREREQUISITESSimple Math, Repeated Squaring PROBLEMYou are given three integers d, m and N in the following relation x^{d} + y^{d} + z^{d} ≡ m, modulo N Find the number of solutions of the above equation where 0 ≤ x, y, z ≤ U EXPLANATIONThe first observation to be made is that the value of N is very small. We already know that a^{b} = (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
Let us say that
Now, we can iterate through the list of unique solutions (X, Y, Z) for X = 0 to N1 for Y = 0 to N1 for Z = 0 to N1 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(N^{3}). 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
is numberofsols(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 + numberofsols(X) * numberofsols(Y) * numberofsols(Z) Thus, the answer can be found in O(N^{3}) time. CODING COMMENTARYThe answer has to be found modulo 10^{9</sup+7}. This leaves a lot of scope for integer overflow. Make sure that your implementation uses 64bit integers for all intermediate results, at the least. 64bit integers can handle the overflow of multiplying two 32bit integers, but not three. You must find the modular result after each product. SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 12 Aug '13, 15:21

I also used the nested loop procedure. But instead on looping on
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? answered 13 Aug '13, 18:04
How does the condition
(13 Aug '13, 18:22)
I also did like you. See this solution as reference http://www.codechef.com/viewsolution/2464513
(14 Aug '13, 00:19)
maybe your pow function has a bug when modulo = 1 . it was my bug , hope this helps.
(14 Aug '13, 01:52)

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 answered 12 Aug '13, 19:52

the trick behind upperlimit of N is really good and was not easy to find out...... answered 20 Aug '13, 10:39

Ah! My solution, just like the editorial!
Why not X will always be less then U%N in numberofsols?