問題一覧 > 通常問題

No.321 (P,Q)-Santa and the Children of the City

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 113
作問者 : kuuso1
お気に入りにしたユーザー ProblemId : 849 / 自分の提出
問題文最終更新日: 2026-06-25 02:22:29
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Show the original
Advent Calendar Contest 2015 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。