-2

how to calculate (A*B*C)%10000007 where A,B,C can be maximum 10^18

Sumurai8
  • 20,333
  • 11
  • 66
  • 100
Amar J. Kachari
  • 9
  • 1
  • Using maths. Did you have a specific language in which you were trying to implement this? If so, you'll need to tag the question with that language, or this is doomed to be closed. – user229044 Jan 07 '13 at 04:06
  • Hello and welcome to stackoverflow.com. Please take some time to read the [FAQ](http://stackoverflow.com/faq), especially the sections named [" What kind of questions can I ask here?"](http://stackoverflow.com/faq#questions) and ["What kind of questions should I not ask here?"](http://stackoverflow.com/faq#dontask). I also recommend you read the sites http://mattgemmell.com/2008/12/08/what-have-you-tried/ and http://sscce.org/. – Some programmer dude Jan 07 '13 at 06:09
  • possible duplicate of [Need help in mod 1000000007 questions](http://stackoverflow.com/questions/9169167/need-help-in-mod-1000000007-questions) – Sumurai8 Feb 15 '14 at 10:47

1 Answers1

2

Let I = 10000007, so

  • A = n1 * I + X1
  • B = n2 * I + X2
  • C = n3 * I + X3

A * B => (n1 * I + X1) (n2 * I + X2) => n1 * n2 * I^2 + n1 * X2 * I + n2 * X1 * I + X1 * X2 Only X1 * X2 can't div by I

Hence, A * B % I === X1 * X2 % I === (A % I) * (B % I) % I

Therefore (A * B * C) % I === [(A % I) * (B % I) % I] * (C % I) % I

redraiment
  • 111
  • 2
  • 7