A silly question...

Правка en2, от roll_no_1, 2018-06-22 19:58:35

This question might sound a little silly, but I was not able to figure the solution to this.

Say, I want to compute an expression of the form (a * b) / c, and I want to do it modulo 13. Now, if a = 13, b = 3, c = 13, then the answer clearly is 3. But if I try to do it this way (((a % 13) * (b % 13)) * inv(c % 13)) % 13, where inv(x) return the multiplicative inverse of x modulo 13, it will not work out. So, how to work around this one ?

[Edit] Magumi_Tadokoro provided a nice workaround for this one in the comments. But there's another thing I would want to ask. The expression above is a very common expression, and the problem mentioned might also have occurred for other similar expressions, but I haven't seen anyone trying to do something special to avoid this in any cf problem. Is it that even the setters do not use this in their problems, so as to avoid making use of this unconventional way of doing this kind of computation in modular arithmetic ?

Теги maths, modular arithmetic, calculation, modular inverse

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский roll_no_1 2018-06-22 19:58:35 526 Tiny change: 'this one ?' -> 'this one ?\n\n[Edit][user:Megumi_Tadokoro] '
en1 Английский roll_no_1 2018-06-22 08:28:04 462 Initial revision (published)