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?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | Dominater069 | 154 |
| 8 | nor | 154 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 14.11.2024 08:37:01 (l3).
Десктопная версия, переключиться на мобильную.
При поддержке
Please use the Chinese Remainder Theorem.
How can I use Chinese Remainder Theorem when N,M aren't coprimes ?
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).
T*(d^-1) ≡ x/d mod N/d
T*(d^-1) ≡ y/d mod M/d
This way ?
Just T ≡ (x % D) mod D, T ≡ (y % D) mod D, T ≡ (x % (N / D)) mod (N / D), T ≡ (y % (M / D)) mod (M / D)
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.