Description
You are encountered with a traditional problem concerning the sums of powers.
Given two integers $n$ and $k$. Let $f(i)=i^k$, please evaluate the sum $f(1)+f(2)+...+f(n)$. The problem is simple as it looks, apart from the value of $n$ in this question is quite large.
Can you figure the answer out? Since the answer may be too large, please output the answer modulo $10^9+7$.
Given two integers $n$ and $k$. Let $f(i)=i^k$, please evaluate the sum $f(1)+f(2)+...+f(n)$. The problem is simple as it looks, apart from the value of $n$ in this question is quite large.
Can you figure the answer out? Since the answer may be too large, please output the answer modulo $10^9+7$.
Input
The first line of the input contains an integer $T(1leq Tleq20)$, denoting the number of test cases.
Each of the following $T$ lines contains two integers $n(1leq nleq 10000)$ and $k(0leq kleq 5)$.
Each of the following $T$ lines contains two integers $n(1leq nleq 10000)$ and $k(0leq kleq 5)$.
Output
For each test case, print a single line containing an integer modulo $10^9+7$.
Sample Input
3
2 5
4 2
4 1
Sample Output
33
30
10
题目意思:给定两个数n,k。求1的k次方 + 2的k次方 + ....+ n的k次方。结果会很大,所以要对10的9次方+7取余。
解题思路:把1-n的每个数的k次方加起来,求幂的时候使用快速幂,值得一提的是数非常大,因此在快速幂求幂的过程中, 每一步也要对10的9次方+7取余。
1 #include<stdio.h> 2 #define MAX 1000000007 3 #define ll long long int 4 ll test(int n,int k) 5 { 6 ll i,t; 7 t=1; 8 for(i=1; i<=k; i++) 9 { 10 t=(t*n)%MAX; 11 } 12 return t; 13 } 14 int main() 15 { 16 ll n,k,sum,i,t; 17 while(scanf("%lld",&t)!=EOF) 18 { 19 while(t--) 20 { 21 sum=0; 22 scanf("%lld%lld",&n,&k); 23 for(i=1; i<=n; i++) 24 { 25 sum=(sum+test(i,k))%MAX; 26 } 27 printf("%lld ",sum); 28 } 29 } 30 return 0; 31 }