akzytr's blog

B. Make Almost Equal With Mod(Modular arithmetic)
By akzytr, history, 2 months ago, In English

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?

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
2 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      well n*m = (n-1)*m + m so there's that and subtracting n by 1 makes it even

      → Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    More readable now
    → Reply