技術室奥プログラミングコンテスト#2 D - エンブレム（Emblem）

問題: D: エンブレム（Emblem） - 技術室奥プログラミングコンテスト#2 | AtCoder
解説: http://www.slideshare.net/maroonrk/ss-64770318

解法

Hは個数に関係なくて、KとWの比のみで決まるため、H=K/gcd(K,W), W=W/gcd(K,W)とする。
そうすると、x+y mod 2 が一定となる点を全て通ることとなる(x,yは1ずつ増えるか、片方が1増えてもう片方が1減る場合しかない)
交点はその中で0

コード

感想

• Hが関係ない、H=Kのとき格子点上に乗る、格子点上に乗るときはx+yが一定、というところまではわかっていたが、WとKの比で決まる、x+y mod 2が一定になる、x+y=0 mod 2となる点を全て通るというところがわかっていなかった
• こういう数学ゲー苦手