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

ID: 16263

传统题

4000ms

256MiB

难度: (无)

上传者:

标签>

数学

数论

洲阁筛

集训队互测

2019

题目描述

小 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$ 取模的结果。

5 1 998244353

500 5 1000000000

365511168

142857 1 1000000009

998244353 998244353 998244353

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