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

Description

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

Input

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

Output

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

Sample Input

1 
2 3

Sample Output

9

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 = 10000;

inline int read()
{
    int f=1,x=0;
    char c=getchar();

    while(c<'0' || c>'9')
    {
        if(c=='-')f=-1;
        c=getchar();
    }

    while(c>='0' && c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }

    return f*x;
}

inline int Qpow(int a,int b)
{
    int r=1;

    while(b)
    {
        if(b&1)
        {
            r=r*a%mod;
        }

        a=a*a%mod;

        b=b>>1;
    }

    return r%mod;
}

int t,a,b,ans,sum;

int main()
{
    t=read();

    while(t--)
    {
        a=read(),b=read();

        ans=0,sum=a/mod;
        
        a=a%mod;

        for(register int i=1; i<=mod; i++)
        {
            if(i<=a)
            {
                ans=(ans+(sum+1)*Qpow(i,b))%mod;
            }
            else 
            {
                ans=(ans+sum*Qpow(i,b))%mod;
            }
        }
        
        printf("%d
",ans);
    }
    
    return 0;
}