#PQJ311x8453. QOJ 311_8453
QOJ 311_8453
标题: 整点计数 - Problem - QOJ.ac
#8453. 整点计数
The problem was used in the following contests:
小 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。
输出格式
一行一个整数 Ans,表示能量总量对 P 取模的结果。
样例数据
样例输入
5 1 998244353
样例输出
28
样例解释
样例输入中 k=1,不难发现此时小 X 需要计算的就是距原点 5 单位内,且至原点距离为整数的整点个数,对 998244353 取模的结果。
形如 (x,0),(−x,0),(0,x),(0,−x) 的符合要求的整点有 4×5=20 个;除了以上整点以外,还有 (3,4),(−3,4),(3,−4),(−3,−4),(4,3),(−4,3),(4,−3),(−4,−3) 共 8 个符合要求的整点,总计 28 个。
样例输入
500 5 1000000000
样例输出
365511168
样例输入
142857 1 1000000009
样例输出
2481012
样例输入
998244353 998244353 998244353
样例输出
637246480
子任务
对于所有测试数据,保证 1≤N,k≤1011,108≤P≤109+9。
测试点编号 分值 N k P 1 3 ≤1000 ≤5 P 是质数 2 3 ≤8×103 3 6 ≤2×105 4 6 ≤5×105 5 5 ≤3×106 6 5 ≤2×107 7 5 8 5 9 8 ≤2×108 =1 10 8 11 8 =2 12 8 13 1 ≤109 =15 P 是 2 的次幂 14 1 =18 15 4 ≤109 P 是质数 16 4 ≤1010 17 4 18 4 19 6 ≤1011 ≤1011 没有额外的限制 20 6