yukicoder No.321 (P,Q)-サンタと街の子供たち
問題文
http://yukicoder.me/problems/849
解法
この問題を見て何となくナイト巡回問題を思い出していた。
ナイト巡回問題ではすべてのマスに移動できたはずなので、一般化してもすべてのマスに移動できるのではないかと思ったが、サンプル4が合わない。
さて、どうしようか。
とりあえずP,Qが互いに素のときを考える。
実験してみると移動可能範囲は次の2パターンしかないことがわかる。
1つ目のパターンになるのは、PとQがともに奇数のとき。何故なのかは市松模様から察してください。
yukicoder No.321 (P,Q)-サンタと街の子供たち
いろいろ迷走してた。実験は重要(本当に重要)。
追記
ガウス整数を使うと解ける。$P+Qi$ の倍数と $Q+Pi$ の倍数の和として表せる数全体は、$P+Qi$ と $Q+Pi$ の最大公約数の倍数全体と一致する。これは整数でいう $a$ の倍数と $b$ の倍数の和として表せる数全体は、$a$ と $b$ の最大公約数の倍数全体と一致するということに対応する。