19214 Trees in a Wood.

問題

2次元平面の格子点(座標がどちらも整数の点)に木が植えてある。原点に立っていて、任意の方向を見ることができるが、木がある場合はその後ろにある木は見ることができない。範囲-a<=x<=a,-b<=y<=bに木が植えてあるとき、すべての木のうち何%の木が見えるか。

考え方

対称性から第1象限の部分だけ考えて4倍すればよいことがわかる。

なので第1象限で、x=iのとき、いくつの木が見えるかを考える。
x=iのとき、y=iまでの個数はオイラーのφ関数の値と同じで、それ以降は周期的であることがわかる。
なので、bをiで割った商をaa、剰余をbbとすれば、x=iのときy=bまでの個数はaa*phi(i)+{1からbbまででiと互いに素な個数}になる。
後ろの部分の計算はaが2000程度までなので実際に1からbbまででgcdを計算して値が1(すなわち互いに素なもの)の個数を数えればよい。