Jrax's blog

By Jrax, history, 4 weeks 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  

»
4 weeks ago, # |
  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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
»
4 weeks ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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

code