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?
# | User | Rating |
---|---|---|
1 | ecnerwala | 3648 |
2 | Benq | 3580 |
3 | orzdevinwang | 3570 |
4 | cnnfls_csy | 3569 |
5 | Geothermal | 3568 |
6 | tourist | 3565 |
7 | maroonrk | 3530 |
8 | Radewoosh | 3520 |
9 | Um_nik | 3481 |
10 | jiangly | 3467 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | adamant | 164 |
2 | awoo | 164 |
4 | TheScrasse | 160 |
5 | nor | 159 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 150 |
8 | SecondThread | 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?
Name |
---|
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.