eighty's blog

the remainder of a big integer
By eighty, history, 9 years ago, In English

Hi Everyone.

Now I'm wondering about how to count (a*b) % c? 1 <= a,b,c <=10^18.

Any advice?

Thank you.

  • Vote: I like it
  • +18
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
9 years ago, hide # |
 
Vote: I like it +23 Vote: I do not like it

  1. You can check if your judge allows int128

  2. You can write your own int128 class (it's a lot easier than general bignum). It's harder than 3. but faster.

  3. You can use algorithm similar to fast exponentiation. Instead of a*a*a*...*a (b times) you calculate a+a+a+...+a (b times) so just change * to + in your favorite quick power implementation.

→ Reply
»
9 years ago, hide # |
← Rev. 2  
Vote: I like it +5 Vote: I do not like it

"Binary multiply" O(log(min(a, b))) :

code

→ Reply