Voldemort's blog

Voldemort's blog

我好菜啊

题解 P1630 【求和】

posted on 2020-07-06 11:35:10 | under 题解 |

题解 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

#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;
}