×

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) =
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.

This question is marked "community wiki".

2.4k128183169
accept rate: 14%

Ah! My solution, just like the editorial!

(12 Aug '13, 16:02)

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

(20 Aug '13, 07:46)

 1 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? answered 13 Aug '13, 18:04 524●1●6●10 accept rate: 17% How does the condition (i+j+k) % N == m mean that xd ≡ i(mod n), and so on? (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) karan1735★ maybe your pow function has a bug when modulo = 1 . it was my bug , hope this helps. (14 Aug '13, 01:52)
 1 What part of this solution is DP ? answered 14 Aug '13, 02:47 3★a2n3k7it 16 accept rate: 0% I had not tagged the problem as Dynamic Programming. Have removed it from the PREREQUISITES as well. (14 Aug '13, 12:21)
 0 what is wrong with my solution I am using the same concept as given http://www.codechef.com/viewsolution/2504889 please find the bug in my code. Thanks! answered 12 Aug '13, 17:48 151●3●5●12 accept rate: 0%
 0 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 5★a_g2009 85●2●3●7 accept rate: 0%
 0 This problem can be done using DP in O(n^2) time. answered 16 Aug '13, 10:29 1 accept rate: 0%
 0 the trick behind upperlimit of N is really good and was not easy to find out...... answered 20 Aug '13, 10:39 16●1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,026
×3,458
×1,897
×281
×150
×27

question asked: 12 Aug '13, 15:21

question was seen: 5,180 times

last updated: 20 Aug '13, 10:39