求和——快速幂

# 求和

## 题目描述
求 1^b+2^b+…… + a^b 的和除以 10^4 的余数。

## 输入格式
第一行一个整数 N，表示共有 N 组测试数据。
对于每组数据，一行两个整数 a,b。

## 输出格式
对于每组数据，一行一个整数，表示答案。

### 样例输入
1
2 3

### 样例输出
9

【数据】
1 <= N <= 100，1 <= a,b <= 10^9

解析：

当然，只用快速幂是不行的。

当a > 10000 时，a^x 可化为 (a%10000)^x 了。所以我们要存储前i个数的次方和。

然后解得答案就是ans=(a/10000*s[10000]+s[a%10000])%10000。

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef pair<int,int> PII;
const int N=2e6+10,p=10000;
int s[N];
int qmi(int a,int b)
{
    int ans=1;
    while (b)
    {
        if (b&1) ans=ans*a%p;
        b >>=1;
        a=a*a%p;
    }
    return ans;
}
signed main()
{
    ios;
    int t;
    cin>>t;
    while (t--)
    {
        int a,b;
        cin>>a>>b;
        for (int i=1;i<=p;i++) s[i]=(s[i-1]+qmi(i,b))%p;
        int ans=(a/p*s[p]+s[a%p])%p;
        cout<<ans;
    }
    return 0;
}