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?
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 | jiangly | 3640 |
2 | Benq | 3593 |
3 | tourist | 3572 |
4 | orzdevinwang | 3561 |
5 | cnnfls_csy | 3539 |
6 | ecnerwala | 3534 |
7 | Radewoosh | 3532 |
8 | gyh20 | 3447 |
9 | Rebelz | 3409 |
10 | Geothermal | 3408 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 173 |
2 | adamant | 164 |
3 | awoo | 161 |
4 | TheScrasse | 160 |
5 | nor | 159 |
6 | maroonrk | 156 |
7 | SecondThread | 152 |
8 | pajenegod | 146 |
9 | BledDest | 144 |
10 | Um_nik | 143 |
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.