A Simple But Difficult Problem
Time Limit: 5000ms
Memory Limit: 65536KB
64-bit integer IO format: %lld Java class name: Main计算前n个正整数的k次幂之和：
结果可能会非常非常大，输出结果的最后5位即可。
Input
输入数据有多组。每组数据一行，每行包括两个整数n和k (1<=n<=1,000,000,000,1<=k<=1000)。
输入数据以-1 -1 结束。
Output
对每一组输入数据，输出单独一行，包括一个整数，给出对应的答案。
Sample Input
100 1 100 2 -1 -1
Sample Output
05050 38350
Source
解题思路：快速幂解决超时问题。
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<string>
#include<iostream>
#include<queue>
#include<vector>
#include<set>
using namespace std;
typedef long long LL;
#define mid (L+R)/2
#define lson rt*2,L,mid
#define rson rt*2+1,mid+1,R
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 300;
const int mod = 1e5;
LL qpowmod(LL n,LL k){
LL ret = 1;
while(k){
if(k&1)
ret = (ret*n) % mod;
k = k>>1;
n = n*n % mod;
}
return ret;
}
int main(){
LL n, k;
while(scanf("%lld%lld",&n,&k)!=EOF){
if(n==-1 && k==-1) break;
LL sum = 0;
LL mo = n%mod, quotient = n/mod;
if(quotient){
for(LL i = 1;i <= mod; i++){
sum = (sum + qpowmod(i,k)) % mod;
}
sum = (sum*quotient) % mod;
}
for(LL i = 1; i <= mo; i++){
sum = (sum + qpowmod(i,k))%mod;
}
printf("%05lld
",sum);
}
return 0;
}