题解 P1630 【求和】
TRZ_2007
2020-07-06 11:35:10
**题解 [P1630 【求和】](https://www.luogu.com.cn/problem/P1630)**
# Description
给定 $n$ 个 $a$ 和 $b$，求 $\sum\limits_{i=1}^a i^b$ 的后四位。
# Solution
## 法1：暴力
对于每一对 $a$ 和 $b$，使用**快速幂**计算出 $\sum\limits_{i=1}^a i^b$ 后进行处理，时间复杂度 $\Theta(N\times a\log b)$ ，期望得分30pts。
## 法2：前缀和
我们发现模数只有10000，而 $a$ 可能会达到 $10^9$，因此会有许多数被重复计算，于是采用前缀和。由于当时大佬们的古怪方法看不懂，于是我自己推了一遍。设$i=10000k+y$，可得：
$$\begin{aligned}\sum\limits_{i=1}^ai^b&=\sum\limits_{i=1}^a(10000k+y)^b\\&=(10000k)^b+C_b^1(10000k)^{b-1}\times y+C_b^2(10000k)^{b-2}\times y^2+\dots+C_b^{b-1}(10000k)\times y^{b-1}+y^b\end{aligned}$$
将其对10000取模，得：
$$\begin{aligned}\sum\limits_{i=1}^ai^b&=(\sum\limits_{i=0}^{10000}i^b\times\frac{a}{10000})\%10000+\sum\limits_{i=0}^{a\%10000}i^b\%10000\end{aligned}$$
其中 $(\sum\limits_{i=0}^{10000}i^b\times\frac{a}{10000})\%10000)$ 这一部分我们可以用前缀和来计算，后面的一部分暴力解决。
最后算法的时间复杂度为$\Theta(N\times M\log b)$，其中 $M$ 是模数，为10000。期望得分100pts。
# Code
```cpp
#include <bits/stdc++.h>
using namespace std;
#define Mod 10000 //模数
int T,a,b;
int qpow(int x,int p) { //快速幂
long long ans = 1;
while(p) {
if(p & 1) ans = (ans * x) % Mod;
x = (x * x) % Mod;
p = p / 2;
}
return ans % Mod;
}
int solve() {
int k = a / Mod;
long long cnt = 0;
a %= Mod;
for(int i = 1;i <= Mod;i++) {
if(i <= a) { //如果这是多余的一部分
cnt = (cnt + (k + 1) * qpow(i,b)) % Mod; //要多算一次
}else {
cnt = (cnt + k * qpow(i,b)) % Mod; //不然就算a/10000次
}
}
return cnt;
}
int main() {
scanf("%d",&T);
while(T--) {
scanf("%d %d",&a,&b);
printf("%d\n",solve());
}
return 0;
}
```