시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
0.2 초 (추가 시간 없음) | 16 MB | 189 | 34 | 30 | 19.231% |
정수론을 응용하자. 실수부와 허수부가 정수인 복소수를 가우시안 수라고 한다.
\begin{equation*}
G=\left\{x+yi\::\:x,y\in\mathbb{Z}\right\},\qquad\text{where}\quad i^2=-1
\end{equation*}
가우시안 수로 정수에서의 약수, 공약수, 최대공약수의 개념이 확장이 가능하다.
두 가우시안 수가 주어졌을 때, 두 수의 모든 최대공약수를 구하는 프로그램을 작성하시오.
첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 테스트 케이스는 최대 1,000개 주어진다.
둘째 줄부터 $(T+1)$번째 줄에 걸쳐 각 줄마다 하나의 테스트 케이스가 주어진다. 각 테스트 케이스는 $-10^9$ 이상, $10^9$ 이하인 4개의 정수 $a,b,c,d$가 공백으로 구분해 주어진다. 이 입력은 가우시안 수 $n=a+bi$, $m=c+di$에 해당한다. $a=b=0$ 혹은 $c=d=0$인 경우는 주어지지 않는다.
가우시안 수 $x+yi$는 $x$를 출력하고 공백을 두고 $y$를 출력하는 방식으로 출력한다. 각 테스트 케이스마다 첫 줄에는 최대공약수의 수를 출력하고, 두 번째 줄에는 최대공약수들을 lexicographic order으로 출력한다. 즉, $a<c$ 혹은 $a=c$와 $b<d$일 때, $a+bi$를 $c+di$보다 먼저 출력한다.
양의 정수에 해당하는 가우시안 수만 주어진다. 즉, $a,c>0$과 $b=d=0$을 만족한다.
$-10^3\leq a,b,c,d\leq 10^3$을 만족한다.
추가 제한 조건이 없다.
3 6 0 9 0 2 1 -2 -1 6 -7 3 5
4 -3 0 0 -3 0 3 3 0 4 -2 -1 -1 2 1 -2 2 1 4 -4 -1 -1 4 1 -4 4 1
최대공약수는 정수에서도 유일하지 않다. 예를들어 정수 $g$가 두 정수 $n,m$의 최대공약수라면, $-g$도 $n,m$의 최대공약수이다.
University > 광주과학기술원 > 광주과학기술원 HOLICS 알고리즘 대회 2018 C번