贡献名单

想法	标程	数据	验题	题解
喵仔牛奶		035966_L3	krjt & 卷王	035966_L3

题目描述

定义：

$$f(n)=\sum_{i=1} ^{n} \sum_{j=1} ^{i} \sum_{k=1} ^{j} \sum_{l=1} ^{k} {\left( \frac{ij}{k} + \prod_{p=1} ^{j} \begin{cases} p^2&2 \mid p \\ \newline p&2 \nmid p \end{cases} \text{ } \right) } $$

试求 $f(1) \sim f(n)$ 的值。答案对一个给定的质数 $m$ 取模。

输入格式

一行，两个正整数，$n,m$。

输出格式

$n$ 行，每行一个整数，对 $m$ 取模。

样例 #1

样例输入 #1

8 1722436571

样例输出 #1

2
25
152
2277
18957
761668
8278573
573179810

提示

限于篇幅，样例不予解释。

（PS：输出中的 $8$ 个数都是取模前的结果。）

---

测试点编号	$n=$	分值
$1$	$10^1$	$10$
$2$	$10^2$
$3$	$10^3$
$4$	$10^4$	$20$
$5$	$10^5$
$6$	$10^6$	$30$

对于 $100\%$ 的数据，$1 \le n \le 10^6$，$10^9< m< 2 \times 10^9$。保证 $m$ 为质数。

---

提示：

不会算 $\dfrac{b}{a} \bmod p$ 的值？你可以用下面的代码，然后切掉 P2613 和 P1082。

int div(int a,int b,int p){return (a==1)?b:((b+1ll*(a-div(p%a,b%a,a))*p)/a%p);}

警告：传入的参数必须满足以下条件，否则会出现 WA，RE 等问题，后果一概自负。

• $a,b,p<2^{31}.$
• $a \ge 1,b \ge 0,p \ge 2.$
• $a,b < p.$
• $\color{red}\gcd(a,p)=1.$