[C언어] 중국인의 나머지 정리

굳이 수식을 사용할 필요 없이 naive하게 문제를 풀면 된다.

DESCRIPTION

3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 수는 무엇인가?

중국문헌 손자산경(孫子算經) 中 이 문제의 답은 105k+23꼴의 수다. (단, k는 정수)

다시말해 105로 나눈 나머지가 23이면 위의 문제를 만족한다.

이 문제를 일반화하여, n1으로 나누었을 때 r1이 남고, n2로 나누었을 때 r2가 남고, n3로 나누었을 때 r3가 남는 수를 n1, n2, n3의 최소공배수로 나눈 나머지를 구해보자.

INPUT

• Line 1: 입력의 갯수 N (1≤N≤100)

• Line 2~N+1: n1, r1, n2, r2, n3, r3가 입력된다. (0≤n1,n2,n3≤2000, 0≤r1<n1, 0≤r2<n2, 0≤r3<n3)

OUTPUT

• Line 1~N: (n1, n2, n3의 최소공배수)와 (x를 n1, n2, n3의 최소공배수로 나눈 나머지)를 출력한다.