No.2847 Birthday Attack
タグ : / 解いたユーザー数 30
作問者 : 👑
torisasami4
Problem Statement
Alice, a magician, has learned attack magic on the occasion of her birthday, when she came of age.
To use attack magic, she needs to draw a magic circle. Represented on a two-dimensional plane, a magic circle looks as follows.
- For all integers $x,y$ satisfying $1 \leq x \leq X, 1 \leq y \leq Y$ and all integers $r$ satisfying $1 \leq r \leq 10^9$, a circle of radius $r$ centered at the coordinates $(x, y)$ is drawn, $1$ for each such combination.
Since Alice likes yin-yang orbs, she decided to count how many yin-yang orbs the magic circle contains. A yin-yang orb is the figure described below.
- The figure shown below is called the basic yin-yang orb.
- On the $xy$-plane, consider circle A with center $(0, 0)$ and radius $2$, circle B with center $(0, -1)$ and radius $1$, and circle C with center $(0, 1)$ and radius $1$.
- The figure consisting of the whole of circle A, the part of circle B with $x \geq 0$, and the part of circle C with $x \leq 0$ is the basic yin-yang orb.
- A figure similar to the basic yin-yang orb (figures that coincide through scaling by a positive factor, reflection, and rotation are regarded as identical) is called a yin-yang orb.
The basic yin-yang orb is illustrated in the image below.
You are given an integer $M$. Find the number of yin-yang orbs contained in the magic circle, modulo $M$. That is, find the number of parts of the figure of the magic circle that are yin-yang orbs, modulo $M$.
Constraints
- All inputs are integers.
- $1 \leq X, Y \leq 4 \times 10^6$
- $10^8 \leq M \leq 10^9$
Input
The input is given from Standard Input in the following format.
$X$ $Y$ $M$
Output
Output the number of yin-yang orbs contained in the magic circle, modulo $M$.
Sample
Sample 1
Input
3 3 100000000
Output
12
The magic circle contains the $12$ yin-yang orbs shown in the figures below. Note that only circles of radius $2$ or less are drawn in the figures.
Sample 2
Input
4 7 100000000
Output
100
Sample 3
Input
1 1 100000000
Output
0
The magic circle may contain no yin-yang orbs.
Sample 4
Input
70 1003381 998244535
Output
357570745
Output the number of yin-yang orbs modulo $M$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。