問題一覧 > 通常問題

No.2847 Birthday Attack

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 30
作問者 : 👑 AngrySadEight / テスター : 👑 seekworser torisasami4
お気に入りにしたユーザー ProblemId : 11070 / 自分の提出
問題文最終更新日: 2024-07-14 02:25:31
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. Back to the original
yukicoder contest 441 (順位表) の他の問題:

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