Блог пользователя rhezo

Автор rhezo, история, 8 лет назад, По-английски

Suppose we have a number X, and we need to find the modulus of it with N numbers, A1, A2, ..., AN.

Then is it true that if we know the modulus of X when divided by LCM(A1, A2, ..., AN), then we can know the individual remainders when X is divided by these numbers (A1, A2, ..., AN).

Can anyone give me a proof? And also the method of how to find the individual remainders.

I read this on a editorial on HackerEarth.

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can you share the link to the editorial and the problem of the editorial?

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    This is the link. It says " In fact, we need one remainder modulo LCM(1, 2, 3, …, 10) = 2520, to know remainder modulo each possible digit."

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

It's actually really simple, if you stop to think about what all of this means.

If you know X % LCM = m, then X = LCM*c + m. But a1 divides LCM, so X = a1*k*c + m. Therefore, as the first part is divisible by a1, X % a1 = m % a1.