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

内存限制:256 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: cz_xuyixuan

题目描述

小 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

5 1 998244353

样例输出 1

28

样例说明

样例输入中 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

500 5 1000000000

样例输出 2

365511168

样例输入 3

142857 1 1000000009

样例输出 3

2481012

样例输入 4

998244353 998244353 998244353

样例输出 4

637246480

数据范围与提示

对于所有测试数据,保证 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 \leq 8\times 10^3
3 6 \leq 2\times 10^5
4 \leq 5\times 10^5
5 5 \leq 3\times 10^6
6 \leq 2\times 10^7
7
8
9 8 \leq 2\times 10^8 =1
10
11 =2
12
13 1 \leq 10^9 =15 P 2 的次幂
14 =18
15 4 \leq 10^9 P 是质数
16 \leq 10^{10}
17
18
19 6 \leq 10^{11} 没有额外的限制
20