11282: [yosupo] Number Theory - Gcd of Gaussian Integers
[Creator : ]
Description
In this problem, $i$ represents the imaginary unit.
Given Gaussian integers $a_1+b_1i$ and $a_2+b_2i$, find one of their greatest common divisors.
Please refer to the following definitions for Gaussian integers and their greatest common divisors:
- An element of $\mathbb{Z}[i] = \lbrace a+bi\mid a,b\in \mathbb{Z}\rbrace$ is called a Gaussian integer.
- For $x, y \in \mathbb{Z}[i]$, we define $x\mid y$ if there exists a $z$ in $\mathbb{Z}[i]$ such that $y = xz$.
- A Gaussian integer $g$ is a greatest common divisor of $x, y\in \mathbb{Z}[i]$ if, for any $z$ in $\mathbb{Z}[i]$, the condition $z\mid g$ is equivalent to $z\mid x$ and $z\mid y$. Such a $g$ is uniquely determined except for multiples of $\pm 1$ and $\pm i$.
You have $T$ test cases to solve.
Given Gaussian integers $a_1+b_1i$ and $a_2+b_2i$, find one of their greatest common divisors.
Please refer to the following definitions for Gaussian integers and their greatest common divisors:
- An element of $\mathbb{Z}[i] = \lbrace a+bi\mid a,b\in \mathbb{Z}\rbrace$ is called a Gaussian integer.
- For $x, y \in \mathbb{Z}[i]$, we define $x\mid y$ if there exists a $z$ in $\mathbb{Z}[i]$ such that $y = xz$.
- A Gaussian integer $g$ is a greatest common divisor of $x, y\in \mathbb{Z}[i]$ if, for any $z$ in $\mathbb{Z}[i]$, the condition $z\mid g$ is equivalent to $z\mid x$ and $z\mid y$. Such a $g$ is uniquely determined except for multiples of $\pm 1$ and $\pm i$.
You have $T$ test cases to solve.
Input
$T$
$a_1$ $b_1$ $a_2$ $b_2$
$\vdots$
$a_1$ $b_1$ $a_2$ $b_2$
$a_1$ $b_1$ $a_2$ $b_2$
$\vdots$
$a_1$ $b_1$ $a_2$ $b_2$
Output
When $a+bi$ is a greatest common divisor of $a_1+b_1i$ and $a_2+b_2i$, output $a$ and $b$.
$a$ $b$
$a$ $b$
Constraints
- $1 \leq T \leq 10^5$
- $-1\times 10^9 \leq a_1, b_1, a_2, b_2 \leq 1\times 10^9$
- $-1\times 10^9 \leq a_1, b_1, a_2, b_2 \leq 1\times 10^9$
Sample 1 Input
8
8 0 6 0
0 0 0 0
0 0 4 8
4 0 6 2
1 2 3 4
1 -2 3 4
1 -3 5 -7
-344235 225420 -33882 162741
Sample 1 Output
2 0
0 0
4 8
-2 -2
1 0
1 -2
-1 1
-456 123
For the first test case, in addition to `2 0`, the following answers are also correct: `-2 0`, `0 2`, and `0 -2`.