問題概要
問題文 → ■
Gauss 整数環における gcd の計算です．基本的な定義は問題文を見てください．本解説は，高校数学レベルの前提知識で十分読めるように書いていると思います．
Gauss 整数環の性質
【Gauss 整数の共役・ノルム】
$a=x+yi\in\Z[i]$ （$a,b\in \Z$）に対して，その共役を $\overline{a}=x-yi$ と定義する．さらに $a$ のノルムを $N(a)=a\overline{a}=x^2+y^2$ と定義する．
Gauss 整数の共役は，複素数の共役の Gauss 整数への制限に一致します．ノルムは複素絶対値の $2$ 乗です．複素数の場合のこれらの性質から，$\overline{ab}=\overline{a}\overline{b}$ や $N(ab)=N(a)N(b)$ が成り立ちます．
【Gauss 整数の除法】
$a,b\in \Z[i]$ とし $b\neq 0$ であるとき，$a=bq+r$ かつ $N(b)>N(r)$ を満たす $b,r \in \Z[i]$ が存在する．さらに $\frac12 N(b)\geq N(r)$ となるように $q,r$ をとることもできる．
このような $q,r$ は $a$ を $b$ で割ったときの商・余りに相当するものです．前半の性質は，代数学の用語を使うと「$\Z[i]$ とノルム $N$ の組は Euclid 整域 をなす」ということもできます．
証明します．まず $\C$ における商 $c=a/b \in \C$ を考えます．$c$ に Euclid 距離の意味で最も近い $\Z[i]$ の点（複素数平面上の格子点）を $q$ とします．$r=a-bq$ とします．
このとき，$|c-q|\leq \sqrt{1/2}$ となることが分かります．したがって $|r|=|a-bq|=|bc-bq|\leq |b|\sqrt{1/2}$ となるので両辺を $2$ 乗して $N(r)\leq \frac{1}{2}N(b)$ が得られます．
なお，$q,r$ は一意ではないことに注意してください．例えば $a=1,b=2$ の場合 $(q,r)=(0,1), (1,-2)$ という 2 つの選択があります．$\Z$ の除法では余りを最小非負整数にとるという定義が十分一般的だと言えると思いますが，Gauss 整数環の除法ではこのような状況で，どちらかを標準的な商・余りとするような十分な合意が得られている定義は存在しないと思います．
【Euclid の互除法】
$a,b\in \Z[i]$ とするとき，ある $g$ が存在して次を満たす．
(1) $g\mid a$, $g\mid b$．
(2) ある $x,y\in \Z[i]$ が存在して $g=ax+by$ が成り立つ．
さらにこのような $g,x,y$ を求める $O(\log \min(N(a),N(b)))$ 時間アルゴリズムが存在する．
Gauss 整数環において余りのノルムを小さくするような除法が可能で，ここから初等整数論でもよく知られている Euclid の互除法をほとんどそのまま Gauss 整数に適用することができます（適切な除法が定義できる環を Euclid 環と呼ぶのもこの性質からきている呼称です）．
除法のところで行った余りの評価 $\frac12 N(b)\geq N(r)$ が計算量評価を与えます．
【最大公約数】
上の $g$ を $a,b$ の最大公約数という．最大公約数 $g$ は以下を満たす：$c\mid g \iff c\mid a \land c\mid b$.
公約数の中である意味最大のものというような主張になっていて，最大公約数と呼ぶ妥当性がありそうです．
証明を確認します．$\implies$ は $g\mid a,g\mid b$ から分かります．$\impliedby$ は $g=ax+by$ という $x,y$ の存在から分かります．
最大公約数は一意ではありません．$g_1,g_2$ がどちらも最大公約数であるとし，これらは $0$ でないとすると $g_1\mid g_2, g_2\mid g_1$ であることが分かります．したがって $g_1=xg_2, g_2=g_1y$ となる $x,y$ がとれますが，このとき $xy=1$ より $N(x)N(y)=N(1)=1$ なので $x,y\in \{\pm 1,\pm i\}$ が分かります（このような $x,y$ は $\Z[i]$ の単数と呼ばれるものです）．このことなどから，一般には $g$ が最大公約数のひとつであるとき，最大公約数は $g, ig, -g, -ig$ の $4$ つです．
これら $4$ つについても，そのうちどれかひとつを指して最大公約数と呼ぶということは，私の知る限りはあまり積極的には行われていないと思います（第一象限に入るものを採用，というようなことはやろうと思えばできますが）．
解法
結局，本問は，与えられた $2$ つの Gauss 整数の最大公約数を，Euclid の互除法で求めるという手法で解くことができます．互除法の各ステップで除法が必要になりますが，これを行う具体的な方法についても上の証明で与えました．
計算量は入力される Gauss 整数の実部・虚部の絶対値の最大値を $A$ とすると $O(\log A)$ 時間です．
- 解答例 (30ms)
コメント
- かなり Gauss 整数環の gcd を計算するだけに近い問題の例：■
- $p\equiv 1\pmod{4}$ となる素数 $p$ に対して $x^2+y^2=p$ となる整数 $x,y$ を求めるといった応用もあります．まず $p\mid a^2+1=(a+i)(a-i)$ となる $a$ をとり，$x+yi=\gcd(p,a+i)$ とすれば条件を満たすことが証明できます．$a$ を求めるには $1\leq b<p$ を乱択して $a=b^{(p-1)/4}\bmod p$ とすると確率 $1/2$ で条件を満たします．
- 上の計算は $p=(x+yi)(x-yi)$ より $p$ の素因数分解を求めているということもできます．この計算は，Gauss 整数環における素因数分解に利用できます．
