安利一下洛谷博客
【问题描述】

求表达式的值。
$$ \sum_{i=1}^{kp} i^{2p-1} \mod?p^{2} $$，其中p为素数。

【输入描述】

一行两个整数k，p。

【输出描述】

一行一个整数表示答案。

【样例】

样例输入

1 3

样例输出

6

最喜欢这种题目了，简单明了，言简意赅，通俗易懂，清晰可见，一目了然，不拐弯抹角。。。

但是

真的不好做啊 。。。
此题用到了费马小定理，同余问题，二次展开式（实质上就是$(a+b)^{n}=$一大堆乱七八糟的东西，用了一个如此高级的东西），还有≡（这个叫恒等于，蒟蒻第一次见还以为是全等。。），这道题充分的发挥了人类的智慧，把$\sum$用的淋漓精致，反正我考试的时候肯定想不到

现在开始动工！

首先，我先把结论抛给大家
$$\sum_{i=1}^{p-1} i^{2p-1}\equiv \frac{p(p+1)}{2} (mod?p^{2})$$

好！其中2p-1是奇数哦(题目已经有提示啦)！

现在开始证明这个结论。

把右边的2移到恒等于号的左边，
$$\sum_{i=1}^{p-1} i^{2p-1} + \sum_{i=1}^{p-1} i^{2p-1}\equiv (p+1)p (mod?p^{2})$$
可以理解吧。

再把$\sum_{i=1}^{p-1} i^{2p-1}$从后面往前求和（因为从前往后和从后往前都是一样的呀），就变成
$$\sum_{i=1}^{p-1} i^{2p-1} + \sum_{i=1}^{p-1} (p-i)^{2p-1}\equiv (p+1)p (mod?p^{2})$$

合并
$$\sum_{i=1}^{p-1} [i^{2p-1} + (p-i)^{2p-1}]\equiv (p+1)p (mod?p^{2})$$
开始二次项展开

$$(p-i)^{2p-1}=$$
$$ p^{2p-1}-C(2p-1,1)p^{2p-2}i+...+C(2p-1,2p-2)pi^{2p-2}-i^{2p-1}$$
就这样，再与$i^{2p-1}$抵消，然后注意一点，因为有$(mod ?p^{2})$所以，当p的指数大于等于2的时候就可以被抵消（2p-1,2p-2等都是奇素数，所以肯定都大于二呀），这么抵消后，最后剩下的就是
$$\sum_{i=1}^{p-1}C(2p-1,2p-2)pi^{2p-2}$$
易得
$$C(2p-1,2p-2)=C(2p-1,1)$$
又因为
$$C(2p-1,1)=2p-1$$
所以
$$\sum_{i=1}^{p-1}(2p-1)pi^{2p-2}\equiv p(p+1) (mod?p^{2})$$
（这个式子很重要，以后会用到）
两边式子都有p，同时除以p，注意$mod?p^{2}$也要除以p，原式就变为
$$\sum_{i=1}^{p-1}(2p-1)i^{2p-2}\equiv (p+1) (mod?p)$$
啊，松口气松口气，更难的来了

好吧对于大佬来说很简单费马小定理登场！
我们有
$$i^{p-1}\equiv 1 (mod?p)$$
然后
$$2p-2=2(p-1)$$
所以
$$\sum_{i=1}^{p-1}(2p-1)(i^{p-1})^{2}\equiv (p+1) (mod?p)$$
所以
$$\sum_{i=1}^{p-1}(2p-1)\equiv (p+1) (mod?p)$$
哈哈哈哈额，好开心啊。

前方路长，继续！

因为现在左式求的值是个定值，所以原式变成$(p-1)(2p-1)\equiv (p+1)(mod?p)$
展开
$$2p^{2}-3p+1\equiv (p+1)(mod?p)$$
因为每个都mod p
$$1\equiv 1(mod?p)$$

原式成立！！

前面辣么多都是预处理，现在处理题目给出的式子。

$$ \sum_{i=1}^{kp} i^{2p-1} \mod?p^{2} $$
将题目中的i去除以p，得到的商和余数用i和j来表示，那么也就是$i=ip+j$(注意区分前面的i和后面的i不一样)

所以就很巧妙的把原来的式子转换成了
$$\sum_{i=0}^{k-1} \sum_{j=1}^{p-1} (ip+j)^{2p-1} \mod?p^{2}$$
同样二次项展开，然后就可以转换成
$$\sum_{i=0}^{k-1} \sum_{j=1}^{p-1} [(2p-1)ipj^{2p-1}+j^{2p-1}] \mod?p^{2}$$
乘法分配律
$$\sum_{i=0}^{k-1} \sum_{j=1}^{p-1} (2p-1)ipj^{2p-1}+\sum_{i=0}^{k-1} \sum_{j=1}^{p-1}j^{2p-1} \mod?p^{2}$$
第二个项可以转化成（刚刚预处理时证明的公式）
$$\sum_{i=0}^{k-1} \frac{p(p+1)}{2} $$

再转化成
$$ \frac{kp(p+1)}{2} $$
第一个项则可以用我刚刚说很重要的公式
变成
$$\sum_{i=0}^{k-1} ip(p+1)$$
继续化简
$$\frac{k(k-1)}{2}p(p+1)$$
将两个式子整合，变成
$$\frac{kp(p+1)}{2}+\frac{k(k-1)p(p+1)}{2}$$
没有求和公式了吧
那么我们在合并同类项之后原式
$$\frac{k^{2}p(p+1)}{2}$$

传说中的O(n)算法！哈哈哈

你好，这里落花殇

表达式

原文：https://www.cnblogs.com/candy067/p/11401956.html