题解【CJOJ1236】【复赛】指数序列求和

Description

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

Input

第一行包含一个正整数N，表示有N组测试数据
接下来N行每行包含两个正整数a和b

Output

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

Sample Input

1
2 3

Sample Output

Hint

数据范围：

对于30%数据n≤10，a，b≤1000

对于100%数据n≤100，a，b≤1000000000

Source

位运算，二分，快速幂

Solution

由标签和数据范围可知，这题是个枚举模数的题。（有二分吗）

我们分析之后就会发现a^b和(a+mod)^b对答案的影响是一样的，证明是显然的。

所以说我们对于任意i^b都可以写成(i%mod)^b,那么只需要把mod打表打下来就可以一次计算完了，打表的时候用倍增快速幂即可。

——摘自这里

知道这个后，这就是一个快速幂取模的水题啦！

Code

 #include <bits/stdc++.h>

 using namespace std;

 const int mod = ;

 inline int read()

 {

     int f=,x=;

     char c=getchar();

     while(c<'' || c>'')

     {

         if(c=='-')f=-;

         c=getchar();

     }

     while(c>='' && c<='')

     {

         x=x*+c-'';

         c=getchar();

     }

     return f*x;

 }

 inline int Qpow(int a,int b)

 {

     int r=;

     while(b)

     {

         if(b&)

         {

             r=r*a%mod;

         }

         a=a*a%mod;

         b=b>>;

     }

     return r%mod;

 }

 int t,a,b,ans,sum;

 int main()

 {

     t=read();

     while(t--)

     {

         a=read(),b=read();

         ans=,sum=a/mod;

         a=a%mod;

         for(register int i=; i<=mod; i++)

         {

             if(i<=a)

             {

                 ans=(ans+(sum+)*Qpow(i,b))%mod;

             }

             else

             {

                 ans=(ans+sum*Qpow(i,b))%mod;

             }

         }

         printf("%d\n",ans);

     }

     return ;

 }

巴特西