問題概要
整数 $x, y$ ($x \neq 0$ or $y \neq 0$) が与えられる．
以下の条件を満たす整数 $a, b$ を出力せよ．
- $-10^{ 18 } \leq a, b \leq 10^{ 18 }$
- 二次元平面 $\mathbb R^2$ 上の点 $( 0, 0 ), ( x, y ), ( a, b )$ を頂点とする三角形の面積が $1$ に等しい
制約
- $-10^{ 17 } \leq x, y \leq 10^{ 17 }$
- $( x, y ) \neq ( 0, 0 )$
解法
まず準備として，点 $( x, y ), ( a, b )$ をそれぞれ位置ベクトルだと考えて，$p = \begin{pmatrix} x \\ y \end{pmatrix}, q = \begin{pmatrix} a \\ b \end{pmatrix}$ とします．また，原点を $O = ( 0, 0 )$ と書きます*1．
三角形の面積というと，底辺と高さを使う公式が超有名ですが，今回の設定では「高さってどこよ」という話になるので，まずは別の方法で三角形の面積を求めることを考えます．やや知識がいる気がしますが，ベクトル $p, q$ が「張る」平行四辺形*2の面積の絶対値*3はベクトルの「クロス積」を用いると
\begin{equation*}
ay - bx
\end{equation*}
と書けます．この平行四辺形を線分 $pq$ で「折り返す」と三角形 $Opq$ にできるので，三角形 $Opq$ の面積は
\begin{equation*}
\left| \frac { ay - bx } 2 \right|
\end{equation*}
となります．ちょっと変形すれば本問題は，
\begin{equation*}
| ay - bx | = 2
\end{equation*}
を満たす整数 $a, b$ を探す問題ということになります．
またやや知識な気がしますが，「拡張 Euclid の互除法」というアルゴリズムがあって，これを用いると
\begin{equation*}
ax + by = \gcd( x, y )
\end{equation*}
を満たす整数 $a, b$ を求めることができます．このことを，
\begin{equation*}
\mathrm{ extgcd }( x, y ) = ( a, b ) \quad \text{s.t. $ ax + by = \gcd( x, y )$}
\end{equation*}
と書くことにします．で，先程の式と似た形の式が出てきたわけですが，係数を調整して
\begin{equation*}
( a, b ) = \mathrm{ extgcd }( y, -x )
\end{equation*}
を求めれば，欲しい値っぽいものが手に入ります．ここで $ay - bx = \gcd( y, -x )$ なので左辺は $\gcd( y, -x )$ の倍数となりますが，これを $2$ にしたかったわけなので，$| \gcd( y, -x ) | \geq 3$ なら解はありません．
以下，$| \gcd( y, -x ) | \leq 2$ とします．$| \gcd( y, -x ) | = 2$ のときは，欲しい物が手に入っているのでそのままでよいです．$| \gcd( y, -x ) | = 1$ のときは左辺を $2$ 倍することで望む $a, b$ が手に入ります．まとめると，
\begin{equation*}
\left( \frac 2 { \gcd( y, -x ) } a, \frac 2 { \gcd( y, -x ) } b \right)
\end{equation*}
が欲しかった値になります．他に細かい話もあるのですが，それは公式の解説に任せることにして，これでよいことにします．
コード
// ax + by = gcd( a, b ) となる x, y を求める // 拡張 Euclid の互除法 LL extgcd( LL a, LL b, LL &x, LL &y ); // 中身省略 int main() { IN( LL, X, Y ); // The area of the triangle ( 0, 0 ), ( A, B ), ( X, Y ) // is the half of absolute value of // the cross product ( A, B ) \times ( X, Y ) = AY - BX // B.T.W., Extended GCD computes A, B, s.t. // AX + BY = GCD( X, Y ) LL A, B; const LL g = extgcd( Y, -X, A, B ); if ( 2 < abs( g ) ) { cout << -1 << endl; return 0; } A *= 2 / g; B *= 2 / g; cout << A << ' ' << B << endl; return 0; }
