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

problem

復号は独立。$4$方向でなく計$8$方向であることに注意。

solution

実験。 数学で$O(1 \times N)$。

移動可能な点を列挙すると綺麗な模様になることは直感的に分かる。このことから、とりあえず実験をする。 この結果に、$gcd(P,Q)$の倍数でないような座標には移動できないのは明らかであることを併せると、解ける。

implementation

$(p, q) = (0, 0)$等、$0$の周りに注意。

#!/usr/bin/env python3
import math
p, q = map(int,input().split())
n = int(input())

if p == 0 and q == 0:
    zero = True
elif p == 0 and q == 0:
    gcd = p + q
    even = True
    zero = False
else:
    gcd = math.gcd(p, q)
    even = (p / gcd) % 2 == 0 or (q / gcd) % 2 == 0
    zero = False

ans = 0
for i in range(n):
    x, y = map(int,input().split())
    if zero:
        if x == 0 and y == 0:
            ans += 1
    else:
        if x % gcd == 0 and y % gcd == 0:
            if even:
                ans += 1
            else:
                if ((x / gcd) + (y / gcd)) % 2 == 0:
                    ans += 1
print(ans)