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

Theory Number Problem
Автор MDantas, 12 лет назад, По-английски

Given four integers N,M,x,y ( 1 <= x,y,N,M <= 10^9 ), what's the minimum value of T such that:

T ≡ x mod N

T ≡ y mod M

Can somebody help me?

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

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

Please use the Chinese Remainder Theorem.

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How can I use Chinese Remainder Theorem when N,M aren't coprimes ?

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      You can calculate D = GCD(N, M) and the remainders modulo D, N / D, M / D, and then you'll just need to solve the resulting congruence (if x mod D != y mod D, then, obviously, there is no solution).

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

T=N*k+x, T=M*p+y => N*k+x=M*p+y <=> N*k-M*p=y-x. Now it's Extended Euclid's algorithm problem. Use it to find k and p.

→ Ответить