CODEWITHSUNDEEP
javaalgorithmmodulolargenumber
Kaushik Lele
Kaushik Lele

Reputation: 6637

How to correctly use Mod 10^9+7

In Java, I need to calculate sum of squares of first n numbers i.e. 

1^2 + 2^2+ 3^2+.....+n^2

which is 

n(n+1)(2n+1)/6

OR 

n^3/3 + n^2/2 + n/6

Then I need to calculate another value 

n*(n-1/2)^2

As n is going to be very big answer can be "answer%M" where M is 10^9+7.

I am not able to understand at which point of calculation I should do operation %M. e.g. 

n%M * (n+1)%M (2n+1)%M /  6

or 

(n(n+1)(2n+1)/6)%M

Can you please help me here. Also in general please provide the guidelines for using %M;so that I can decide it next time onward.

Upvotes: 4

Views: 12041

Answers (2)

Paul Hankin
Paul Hankin

Reputation: 58221

(n(n+1)(2n+1)/6)%M is correct in theory and n%M * (n+1)%M * (2n+1)%M / 6 is incorrect.

If n is large, the intermediate calculations of (n(n+1)(2n+1)/6) will overflow your integer type, so the first method is also unsatisfactory.

The general solution for computing a*b/c % M would be to compute the modular inverse of c mod M (say c') and then compute: ((a%M * b%M)%M * c')%M

Here, it's a little simpler as you're dividing by a constant (6) and can find and strike out factors of 2 and 3 in the three terms. Something like this in pseudocode:

n1 := n
n2 := n+1
n3 := 2n+1
if n1 % 2 == 0 { n1 /= 2 } else { n2 /= 2 }
if n1 % 3 == 0 { n1 /= 3 } else if n2 % 3 == 0 { n2 /= 3 } else { n3 /= 3}
return (((n1 % M) * (n2 % M)) % M * (n3 % M)) % M

Upvotes: 8

Alexander Ushakov
Alexander Ushakov

Reputation: 5399

Division by modulo can't be made by / operator: (a/b) % M != ((a % M)/(b % M)) % M, so you need to take modulo only at the end:

(n*(n+1)*(2n+1)/6) % M

For more information read Modulo operation. And don't forget to use BigInteger class for calculations with realy big numbers.

Upvotes: 0

Related Questions