求 1^b+2^b+…+a^b的程序。。注意不要超时

求 1^b+2^b+…+a^b的程序。。注意不要超时

快速幂吗？不用高精度的吧
O(a*logb)，

c++代码
#include 

const int mod = 10000;

int power(int a, int n) {
int s = 1, t = a;
for (; n; n >>= 1) {
if (n&1) s = s * t;
t = t * t;
}
return s;
}

int main() {
int T; scanf("%d", &T);
while (T --) {
int a, b; scanf("%d%d", &a, &b);
int res = 0;
for (int i = 1; i <= a; ++ i)
(res += power(i, b)) %= mod;
printf("%d
", res);
}
return 0;
}应该可以利用循环节再加速，但应该可以A吧。。
有问题可提问。
追问为什么直接调用math.h文件里的pow函数不行？追答那个东西是double型的吧，损精度的吧

http://blog.csdn.net/qq_35546274/article/details/52022222
这个时间复杂度只要10000*logb。