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

Автор WalidMasri, история, 9 лет назад, По-английски

Hello everyone!

i was trying to solve this problem , but the modulo behavior caused me to get WA as a verdict.

When computing the formula  , once n is reduced by modulo, the prime divisors (p1,p2... pk) wont remain divisors of n, hence, getting a non-integer result.

MORE Explanation : Given (n%k)/ m, where m is a divisor of n ... if i performed n%k then divided by m, i will get a non-integer result.

What can i do to avoid such problem?

Thanks!

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

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

You can use the modular multiplicative inverse (109 + 7 is prime).

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

Use this

(a/b)%m = ((a%m)(b^(m-2)%m))%m.

Source