Блог пользователя eighty

the remainder of a big integer
Автор eighty, история, 6 лет назад, По-английски

Hi Everyone.

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

Any advice?

Thank you.

  • Проголосовать: нравится
  • +18
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

  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.

→ Ответить
»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

code

→ Ответить