No.321 (P,Q)-Santa and the Children of the City
Problem Statement
"It is not that Santa comes to good children; rather, the children Santa comes to are the good children."
In Yuki City, a town where cause and effect have been reversed, you are known as the $(P,Q)$ -Santa, the one and only Santa, reigning at the center of the city.
Yuki City is represented by the $(X,Y)$ plane, and you are at the origin $(0,0)$.
The children of the city live on lattice points of Yuki City (coordinates where $X$,$Y$ are both integers).
Your job is to deliver presents at Christmas, but your means of transportation is a sleigh pulled by special reindeer, which has excellent mobility but is restricted in the directions it can move.
As the name $(P,Q)$-Santa suggests, from the current position $(x,y)$ you can move in one move to $(x \pm P,y \pm Q)$ or $(x \pm Q,y \pm P)$.
For example, when $(P,Q)=(1,2)$, if the current position is $s$, you can move to $t$.
.t.t. t...t ..s.. t...t .t.t.
You are a Santa with a very strong sense of responsibility, and with your high mobility you can move any number of times, so you always deliver a present to every child you are able to visit.
Given the coordinates $(X_i,Y_i)$ of each of the $N$ children of the city, find the number of good children living in the city.
Input
$P$ $Q$
$N$
$X_0$ $Y_0$
$X_1$ $Y_1$
$\vdots$
$X_{N-1}$ $Y_{N-1}$
All input values are integers.
$0\le P \le 10^9$
$0\le Q \le 10^9$
$1\le N \le 10^5$
$-10^9 \le X_i \le 10^9$ , $0 \le i < N$
$-10^9 \le Y_i \le 10^9$ , $0 \le i < N$
Output
Output the number of good children on one line. Print a newline at the end.
Sample
Sample 1
Input
2 3 3 2 3 3 -2 -5 -5
Output
3
You can deliver a present to the third child by, for example, moving to $(-2,-3)$ and then moving by $(-3,-2)$.
Sample 2
Input
1 0 3 0 3 4 1 2 2
Output
3
By moving one step at a time vertically and horizontally, you can deliver presents to all the children.
Sample 3
Input
1 2 5 2 6 6 3 2 4 0 0 6 1
Output
5
In my previous job, I worked as a knight in the chess industry. Unlike a bishop, I could go anywhere.
Sample 4
Input
4 12 6 1 4 2 7 4 3 8 4 5 5 6 12
Output
0
There were no good children in this city. Not a single one.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
kuuso1