洛谷1630 求和

Luogu

算法

这是一道数论题。

首先要计算a^b,一定要快速幂。
但是纯循环+快速幂只能得30分,所以分析一下所求:
a^b%10000 = (a+10000)^b%10000
所以先求出$1$到$10000$的$1^b+...+n^b$,放在f数组中。

对于任何数$n$,$n^b$即为(n div 10000 * f[10000] + f[n mod 10000]) mod 10000
即一堆10000加上剩余的再取模。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;
const int MOD=10000;
inline int fastpow(int a,int b) //快速幂
{
    if (b==1) return a%MOD;
    int s=fastpow(a,b/2)%MOD;
    if (b&1) return (s*s%MOD)*(a%MOD)%MOD;
    else return s*s%MOD;
}
int f[MOD+10]; //存幂和
int main()
{
    int t,a,b; scanf("%d",&t);
    while (t--)
    {
        scanf("%d%d",&a,&b); //输入
        for (re int i=1;i<=MOD;i++) f[i]=(f[i-1]+fastpow(i,b))%MOD; //打表,加上再取模orz
        int ans=(a/MOD*f[MOD]+f[a%MOD])%MOD; //计算答案
        printf("%d\n",ans); /:输出
    }
    return 0;
}
最后修改:2019 年 09 月 23 日 10 : 27 PM

发表评论