题解 P1630 【求和】

· · 题解

- 前置知识:

    (a+y)^x=a^x(mod y)

快速幂：比较简单的数论基础，如果没有学过，快速幂传送门

- 当我看到这一题时，我脑子里冒出了两个想法：

  1. 这题的快速幂是妥妥的（√）

  2. 在吗？模数是不是质数？可不可以套逆元？（×） 然而沙雕的我却忽略了模数那小到可怜的大小，显然这一题必须针对模数进行操作，且时间复杂度与x,y无关，所以：

    a^x 可化为 (a%10000)^x

    所以我们只要用一个sum前缀和数组存储前i个数的次方和:

    sum[i]=(sum[i-1]+qpow(i,b))%mod;

然后O(1)求答案：

    ans=n/10000*sum[10000]+sum[n%10000]

详见代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;//同#define LL long long
const LL mod=10000;
LL a,b,ans,sum[10010];
inline LL qpow(LL a,LL p,LL mod){//快速幂模板，求a^p
    LL sum=1;
    while(p){
        if(p&1){
            sum=sum*a%mod;
        }
        a=a*a%mod;
        p>>=1;//通过倍增的方法求幂；
    }
    return sum%mod;
}
int main(){
    LL Time; 
    scanf("%lld",&Time);
    while(Time--){
        scanf("%lld%lld",&a,&b);
        for(register LL i=1;i<=10000;++i){
            sum[i]=(sum[i-1]+qpow(i,b,mod))%mod;//针对模数下手，用数组求出(i<=10000)的前缀和
        }
        ans=(a/10000*sum[10000]+sum[a%10000])%mod;//通过上文所将的前缀和以O(1)求出答案；
        printf("%lld\n",ans);
    }
}

综上所述，预处理O(mod),求值O(1),所以时间复杂度为O(T*mod)，空间复杂度为O(10000)，能够通过评测