| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
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?
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.
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.
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.
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.
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.
You may find A mod (B*n) = a, then A/B = a/B mod n
How does this work exactly? And n is the initial prime modulo, right? (with which we need to find integer division of (A/B) ) ?
Yes. If A = Bnk + a, then
Can you explain me please how to find (A mod (B * n))?
the same way you would do it with any other modulo?