题意：求$\sum_{i=1}^a i^b,a,b\le 10^9$

 

　　暴力只有30分QAQ（本数学蒟蒻当然想不到正解啦）

正解：模数很小，不难(?)想到$i^a%10000=(i+b)^a %10000$

　　　因此只需要预处理$\sum_{i=1}^{10000} i^b$

　　　之后$10001^b%10000=1^b%10000$

　　　　　$10002^b%10000=2^b%10000$

　　　　　$a^b%10000=(a-k*10000)^b%10000$

　　所以$ans=a/10000*f[10000]+f[a%10000]$

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define int long long#define olinr return#define _ 0#define love_nmr 0#define DB double#define mod 10000inline int read(){    int x=0,f=1;    char ch=getchar();    while(!isdigit(ch))    {        if(ch=='-')            f=-f;        ch=getchar();    }    while(isdigit(ch))    {        x=(x<<1)+(x<<3)+(ch^48);        ch=getchar();    }    return x*f;}inline void put(int x){    if(x<0)    {        x=-x;        putchar('-');    }    if(x>9)        put(x/10);    putchar(x%10+'0');}int T;int a;int b;inline int ksm(int x,int y){    int re=1LL;    while(y)    {        if(y&1)            re=re*x%mod;        x=x*x%mod;        y>>=1;    }    return re;}int f[10505];signed main(){    T=read();    while(T--)    {        a=read();        b=read();        f[1]=1;        for(int i=2;i<=mod;i++)            f[i]=(f[i-1]+ksm(i,b))%mod;        put((a/mod*f[mod]+f[a%mod])%mod);        putchar('\n');    }    olinr ~~(0^_^0)+love_nmr;}