P1630 求和

题目描述

求1^b+2^b+……+a^b的和除以10000的余数。

输入输出格式

输入格式：

 

第一行包含一个正整数N，表示共有N组测试数据；

接下来N行，每行包含两个正整数a和b。

【数据规模】

对于30%的数据中，满足N<=10，a,b<=1000;

对于100%的数据中，满足N<=100，a,b<=1000000000;

 

输出格式：

 

共N行，每行一个对应的答案。

 

输入输出样例

输入样例#1： 

12 3

输出样例#1： 

9

 

 

 

快速幂+优化

在我们for循环的时候循环到a是一定不可能的，我们知道在我们取膜的时候a*c%b=a%b*c%b，所以我们利用这个原理，因为是挨着快速乘，他们取膜以后的数也一定是连着的，因此我们直接for循环i位每一个数取膜以后的数，我们还可以知道，当前数如果比a%b小的话，那么我们就有a./b+1个，反之，就有a/b个

#include
     
      #include
      
       #include
       
        #include
        
         #define mod 10000using namespace std;int n,a,b,s,ans;int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();    return x*f;}int qpow(int a,int b){    int res=1;    while(b)    {        if(b&1) res=1ll*res*a%mod;        a=1ll*a*a%mod;b>>=1;    }    return res;}int main(){    n=read();    while(n--)    {        a=read(),b=read();        s=a/mod;a%=mod;ans=0;        for(int i=1;i<=mod;i++)        {            if(i<=a) ans=(ans+1ll*(s+1)*qpow(i,b)%mod)%mod;            else ans=(ans+1ll*s*qpow(i,b)%mod)%mod;        }        printf("%d\n",ans);    }    return 0;}