LibreOJ

3069 「2019 集训队互测 Day 1」整点计数

内存限制：256 MB 时间限制：4000 ms

题目描述

小 X 的姐姐小 F 是一名 X 国的占星师，而作为附魔师的小 X 则需要在占星的过程中辅助小 F。

今夜，空中的星星排列得格外整齐，如果将整个星空抽象成一个平面直角坐标系的话，在每一个整点处，都恰好有一颗星，小 X 和小 F 所在的星就是原点。

距离小 X 和小 F 所在的星相同的星之间是会相互作用的，如果记 $f(x)$ 表示距离小 X 和小 F 所在的星 $x$ 个单位的星星的个数，那么这一系列的星将共计产生 $f(x)^k$ 点能量。

小 F 观察到，在月圆之夜，距离自己和小 X 所在的星恰好整数个单位的星产生的能量将会变得易于收集。并且，由于技术限制，小 F 暂时只能够收集距离自己和小 X 所在的星不超过 $N$ 个单位的星产生的能量。需要特别注意的是，小 X 和小 F 所在的星并不会产生能量。

小 X 要做的，就是帮助小 F 计算此时能够被收集的能量总量。由于能够收集的能量实在太过庞大，小 X 难以确保自己计算毫无失误，因此他希望你能够告诉他这个数值在对某一个数 $P$ 取模后的结果来验证他计算的正确性。

输入格式

一行三个正整数 $N,k,P$。

输出格式

一行一个整数 $\text{Ans}$，表示能量总量对 $P$ 取模的结果。

样例 1

样例输入中 $k=1$，不难发现此时小 $X$ 需要计算的就是距原点 $5$ 单位内，且至原点距离为整数的整点个数，对 $998244353$ 取模的结果。

形如 $(x,0),(-x,0),(0,x),(0,-x)$ 的符合要求的整点有 $4\times 5=20$ 个；除了以上整点以外，还有 $(3,4),(-3,4),(3,-4),(-3,-4),(4,3),(-4,3),(4,-3),(-4,-3)$ 共 $8$ 个符合要求的整点，总计 $28$ 个。

样例 2

样例 3

样例 4

数据范围与提示

对于所有测试数据，保证 $1 \leq N,k \leq 10^{11},10^8 \leq P \leq 10^9+9$。

测试点编号 分值 $N$ $k$ $P$
1 $3$ $\leq 1000$ $\leq 5$ $P$ 是质数
2 $3$ $\leq 8\times 10^3$ $\leq 5$ $P$ 是质数
3 $6$ $\leq 2\times 10^5$ $\leq 5$ $P$ 是质数
4 $6$ $\leq 5\times 10^5$ $\leq 5$ $P$ 是质数
5 $5$ $\leq 3\times 10^6$ $\leq 5$ $P$ 是质数
6 $5$ $\leq 2\times 10^7$ $\leq 5$ $P$ 是质数
7 $5$ $\leq 2\times 10^7$ $\leq 5$ $P$ 是质数
8 $5$ $\leq 2\times 10^7$ $\leq 5$ $P$ 是质数
9 $8$ $\leq 2\times 10^8$ $=1$ $P$ 是质数
10 $8$ $\leq 2\times 10^8$ $=1$ $P$ 是质数
11 $8$ $\leq 2\times 10^8$ $=2$ $P$ 是质数
12 $8$ $\leq 2\times 10^8$ $=2$ $P$ 是质数
13 $1$ $\leq 10^9$ $=15$ $P$ 是 $2$ 的次幂
14 $1$ $\leq 10^9$ $=18$ $P$ 是 $2$ 的次幂
15 $4$ $\leq 10^9$ $\leq 10^9$ $P$ 是质数
16 $4$ $\leq 10^{10}$ $\leq 10^9$ $P$ 是质数
17 $4$ $\leq 10^{10}$ $\leq 10^9$ $P$ 是质数
18 $4$ $\leq 10^{10}$ $\leq 10^9$ $P$ 是质数
19 $6$ $\leq 10^{11}$ $\leq 10^{11}$ 没有额外的限制
20 $6$ $\leq 10^{11}$ $\leq 10^{11}$ 没有额外的限制

样例

样例输入 1

5 1 998244353

样例输出 1

28

样例输入 2

500 5 1000000000

样例输出 2

365511168

样例输入 3

142857 1 1000000009

样例输出 3

2481012

样例输入 4

998244353 998244353 998244353

样例输出 4

637246480