Hide

# Chinese Remainder Theorem (non-relatively prime moduli)

## Input

The first line of input consists of an integers $T$ where $1 \leq T \leq 1000$, the number of test cases. Then follow $T$ lines, each containing four integers $a$, $n$, $b$, $m$ satisfying $1 \leq n, m \leq 10^9$, $0 \leq a < n$, $0 \leq b < m$.

## Output

For each test case, output two integers $x$, $K$, where $K = \mbox{lcm}(n,m)$ and $0 \leq x < K$, giving the solution $x \pmod K$ to the equations $x = a \pmod n, x = b \pmod m$.

Sample Input 1 | Sample Output 1 |
---|---|

3 10000 23000 9000 23000 10000 23000 10000 23000 1234 2000 746 2002 |
no solution 10000 23000 489234 2002000 |

CPU Time limit
1 second

Memory limit
1024 MB

Difficulty
3.9medium

Statistics
Show

Downloads

Author

Source
KTH CSC Popup 2005