yukicoder No.321 (P,Q)-サンタと街の子供たち

問題文

http://yukicoder.me/problems/849

解法

この問題を見て何となくナイト巡回問題を思い出していた。 ナイト巡回問題ではすべてのマスに移動できたはずなので、一般化してもすべてのマスに移動できるのではないかと思ったが、サンプル4が合わない。 さて、どうしようか。

とりあえずP,Qが互いに素のときを考える。

実験してみると移動可能範囲は次の2パターンしかないことがわかる。

f:id:pekempey:20151216192707p:plain

1つ目のパターンになるのは、PとQがともに奇数のとき。何故なのかは市松模様から察してください。

f:id:pekempey:20151216192948p:plain

yukicoder No.321 (P,Q)-サンタと街の子供たち

いろいろ迷走してた。実験は重要(本当に重要)。

追記

ガウス整数を使うと解ける。$P+Qi$ の倍数と $Q+Pi$ の倍数の和として表せる数全体は、$P+Qi$ と $Q+Pi$ の最大公約数の倍数全体と一致する。これは整数でいう $a$ の倍数と $b$ の倍数の和として表せる数全体は、$a$ と $b$ の最大公約数の倍数全体と一致するということに対応する。