#1963. 整点计数

整点计数

整点计数

题目描述

标题: 整点计数 - Problem - QOJ.ac

#8453. 整点计数

Statistics

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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5 1 998244353
28

样例 2

500 5 1000000000
365511168