Tester をしました。詰まったので公式解説の解説を書きます。
主張
ある整数 $p$ を用いて $gcd(A, B)=p^2$ と表せるとき、Odd である。
解説
まず、$A, B$ の公約数の個数は $gcd(A, B)$ の約数の個数です。これの偶奇を求める問題を解きます。
ある数の約数の個数は、ある数を素因数分解し、各素因数の指数 $+1$ をすべて掛け合わせたものです。
これが奇数であるとき、各素因数の指数 $+1$ は必ずすべて奇数です。よって、各素因数の指数は必ずすべて偶数です。
以上より二乗の形であらわせるとき Odd であることがわかりました。また、それ以外の時が Even であることも示せました。
こういうのほとんど書かないので不備などあれば知らせてください。
