No.321

$X, Y$ のどちらかが $P, Q$ の最大公約数で割り切れない場合は明らかに移動できない.

以後はすべて $P, Q$ の最大公約数で割って考える.

まず, $(P, Q) = (0, 0)$ の場合はどこにも移動できないので原点以外は行けない.

$(P, Q) = (0, 1)$ または $(1, 0)$ の場合はサンプル2の場合であり, すべての点に行ける.

$(P, Q) = (1, 1)$ のときは斜め方向にしか移動できないので, $X = Y$ の点以外は行けない.

以下は $P \neq 0, Q \neq 0, P \neq Q$ とする.

サンタが $x$ 座標の $X$ に移動できるとき,

$$X = aP + bQ$$

と表せる.

このときに $y$ 座標の $Y$ は, $bP + aQ$ から偶数回上下に $P$ 移動するか偶数回上下に $Q$ 移動するかできるので,

$$Y = (b+2n)P + (a+2m)Q$$

となる. よって,

$$nP + mQ = \frac{Y - bP - aQ}{2}$$

となり, $n, m$ が存在するためには $(Y - bP - aQ)/2$ が整数になればいい.

ここで,

$$\frac{Y-bP-aQ}{2} = \frac{QY - (X - aP)P - aQ^2}{2Q} = \frac{QY-XP+a(P^2-Q^2)}{2Q}$$

となるので, $P^2 - Q^2$ と $2Q$ が互いに素であれば $a$ が存在するので, すべての点に行ける.

そうでない場合は $g = \gcd(P^2 - Q^2, 2Q)$ として, $QY-XP$ が $g$ で割り切れればやはり $a$ が存在する.