No.2847 Birthday Attack
タグ : / 解いたユーザー数 28
作問者 : 👑
![AngrySadEight](https://pbs.twimg.com/profile_images/1774819988135927808/f4w6hc33.jpg)
![torisasami4](https://pbs.twimg.com/profile_images/1102585635137679360/edE9JNpl.png)
問題文
魔法使いの Alice は,誕生日を迎えて成年になったことをきっかけに,攻撃の魔法を習得しました.
攻撃の魔法を使うには,魔法陣を描く必要があります.魔法陣を二次元平面に表現すると,以下のようになります.
- $1 \leq x \leq X, 1 \leq y \leq Y$ を満たす整数 $x,y$,および $1 \leq r \leq 10^9$ を満たす整数 $r$ のすべてに対して,座標 $(x, y)$ を中心とした半径 $r$ の円が $1$ つずつ描かれている.
Alice は,陰陽玉が好きなので,魔法陣に陰陽玉が何個含まれるかを数えることにしました.陰陽玉とは,以下の図形を表します.
- 以下に示す図形を,基本陰陽玉と呼ぶ.
- $xy$ 平面上において,中心が $(0, 0)$ で半径 $2$ の円 A,中心が $(0, -1)$ で半径 $1$ の円 B,中心が $(0, 1)$ で半径 $1$ の円 C を考える.
- このとき,円 A 全体,円 B の $x \geq 0$ の部分,円 C の $x \leq 0$ の部分からなる図形が,基本陰陽玉である.
- 基本陰陽玉と相似な図形(正の倍率の拡大・縮小および裏返し・回転を行うことにより一致する図形を同一視する)を,陰陽玉と呼ぶ.
基本陰陽玉を図示すると,以下の画像のようになります.
整数 $M$ が与えられます.魔法陣に含まれる陰陽玉の個数を,$M$ で割った余りを求めてください.すなわち,魔法陣の図形の一部分であって,陰陽玉であるものの個数を,$M$ で割った余りを求めてください.
制約
- 入力はすべて整数である.
- $1 \leq X, Y \leq 4 \times 10^6$
- $10^8 \leq M \leq 10^9$
入力
入力は以下の形式で標準入力から与えられる.
$X$ $Y$ $M$
出力
魔法陣に含まれる陰陽玉の個数を $M$ で割った余りを出力せよ.
サンプル
サンプル1
入力
3 3 100000000
出力
12
含まれる陰陽玉は,以下の図に示す $12$ 個となります.なお,図には半径 $2$ 以下の円のみが描かれていることに注意してください.
サンプル2
入力
4 7 100000000
出力
100
サンプル3
入力
1 1 100000000
出力
0
魔法陣に陰陽玉が含まれない場合もあります.
サンプル4
入力
70 1003381 998244535
出力
357570745
陰陽玉の個数を $M$ で割った余りを出力してください.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。