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 | 3757 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 171 |
2 | awoo | 165 |
3 | adamant | 164 |
4 | TheScrasse | 159 |
5 | maroonrk | 155 |
6 | nor | 154 |
7 | -is-this-fft- | 152 |
8 | Petr | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
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?
Название |
---|
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.