| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3845 |
| 2 | jiangly | 3707 |
| 3 | Benq | 3630 |
| 4 | orzdevinwang | 3573 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | jqdai0815 | 3532 |
| 8 | ecnerwala | 3501 |
| 9 | gyh20 | 3447 |
| 10 | Rebelz | 3409 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | adamant | 163 |
| 3 | awoo | 162 |
| 4 | nor | 153 |
| 5 | maroonrk | 152 |
| 6 | -is-this-fft- | 151 |
| 6 | TheScrasse | 151 |
| 8 | Petr | 145 |
| 9 | pajenegod | 144 |
| 10 | orz | 143 |
I could not solve 1909B - Make Almost Equal With Mod on my own and thus looked at the tutorial, which among other things writes the following:
if a % m = k:
a % 2m is either k, or k+m
Is there any proof/concept of modular arithmetic that explains why this is so?
given a % m == k , we can write a as k(<m) + n * m where n is a factor >= 0
now we take a % 2*m , we get (k+n*m) % 2*m , we can take it as following cases :
if n%2==0 then we have a % 2*m = (k+n*m) % 2*m = k
if n%2==1 then we have a % 2*m = (k + m + (n-1)*m) % 2*m = k + m
Thus we can have only two cases that can be shown as above
If we have n%2 = 1
How are we getting
(k + m + (n-1)*m)
Why are we getting the extra +m after k, and also why are we subtracting n by 1?
well n*m = (n-1)*m + m so there's that and subtracting n by 1 makes it even
given $$$a$$$%$$$m==k$$$ , we can write a as $$$k(<m) + n * m$$$ where $$$n$$$ is a factor $$$>= 0$$$
now we take $$$a $$$%$$$ 2*m$$$ , we get $$$(k+n*m) $$$%$$$ 2*m$$$ , we can take it as following cases :
if $$$n$$$%$$$2==0$$$ then we have $$$a $$$%$$$ 2*m = (k+n*m) $$$%$$$ 2*m = k$$$
if $$$n$$$%$$$2==1$$$ then we have $$$a $$$%$$$ 2*m = (k + m + (n-1)*m) $$$%$$$ 2*m = k + m$$$
Thus we can have only two cases that can be shown as above