Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

rhezo's blog

By rhezo, history, 7 years ago,

I need to do integer division, that is floor of A/B. Eg: 5/2 = 2.

Now consider the modulo to be prime, multiplying A with inverse of B and taking modulo is wrong.

What I said above is true because , 6 * inverseOf(2) = 3. But 5 * inverseOf(2) is not equal to 2.

So how can I do this?

• +2

 » 7 years ago, # | ← Rev. 2 →   +37 If I understood correctly, what you want is to find some function f such that given A mod P = a , B mod P = b , then floor(A/B) = f(a,b) . This is obviously impossible. Consider this simple example:Take P = 7. Since floor(11/3) = 3, then f(4,3) should be 3. But since floor(4/3) = 1, then f(4,3) should be 1 and we have a contradiction.
•  » » 7 years ago, # ^ |   0 No I meant that once we have a and b(as defined above), can we find A/B(integer division) as (a*inverse(b)) mod P? But I guess it can't be done.
•  » » » 7 years ago, # ^ |   0 No, we cannot do that. Modular inverse has nothing to do with integer division, even though names sound similar.Another example: suppose P = 11, A = 13 (2 modulo P), B = 2. Then inverse(B) = 6 (because 2·6 = 12 = 1), but A·inverse(B) = 1, which is obviously not the answer expected.
 » 7 years ago, # | ← Rev. 2 →   +21 What about using the fact that Integer division of A by B is same as (A — A % B) / B ? After this you can use modular inverses, either directly if prime or using extended euclid algorithm.
•  » » 7 years ago, # ^ |   -7 Looks good, but for this I would have to maintain A%B too always. Since I wanted to do everything modulo some prime P initially, I would maintain everything modulo P only and it can get messy if B changes over many queries. For a single B, this would work I think.
 » 7 years ago, # |   +5 You may find A mod (B*n) = a, then A/B = a/B mod n
•  » » 7 years ago, # ^ |   0 How does this work exactly? And n is the initial prime modulo, right? (with which we need to find integer division of (A/B) ) ?
•  » » » 7 years ago, # ^ |   +8 Yes. If A = Bnk + a, then
•  » » » » 7 years ago, # ^ |   0 Can you explain me please how to find (A mod (B * n))?
•  » » » » » 7 years ago, # ^ |   +10 the same way you would do it with any other modulo?