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