[問題案] GCD of Gaussian Integers

[NachiaVivias]

Problem name: GCD of Gaussian Integers
Problem ID: gcd_of_gaussian_integers

Problem

$t=0, \ldots ,Q-1$ について、ガウス整数 $a _ t + b _ t i$ , $c _ t + d _ t i$ の最大公約数 $x _ t + y _ t i$ を求めてください。

Constraint

• $1\leq a _ t ^ 2 + b _ t ^ 2$
• $1\leq c _ t ^ 2 + d _ t ^ 2$

Input

$Q$
$a _ 0$ $b _ 0$ $c _ 0$ $d _ 0$
$a _ 1$ $b _ 1$ $c _ 1$ $d _ 1$
$\vdots$
$a _ {Q-1}$ $b _ {Q-1}$ $c _ {Q-1}$ $d _ {Q-1}$

Output

$x _ 0$ $y _ 0$
$x _ 1$ $y _ 1$
$\vdots$
$x _ {Q-1}$ $y _ {Q-1}$

Note

originally posted by hec12 : #3 (comment)

[noshi91]

$\gcd (0, x) = x$ や $\gcd(0, 0) = 0$ も入れて良いのではと思います。

単数倍についてはどうすると良いでしょうか。入力は正規化されていないとして、出力を正規化させるか、なんでも OK にするか。

[NachiaVivias]

単数倍はまず #895 で議論して、その後に $0$ のことを決めるのがよさそうです。

[maspypy]

$0$ は入れてよいと思います。 $4$ 通りのうちいずれかを出力でよいと思います。
$|a_i|\leq 10^9$ という感じの制約がつくのだと思っています。

[maspypy]

出力は単数倍の自由度を認める（ジャッジを実装する）ということでお願いします。

[maspypy]

作業します。