E - Easy Summation

xiaoxiao2021-02-28  5

You are encountered with a traditional problem concerning the sums of powers.  Given two integers  n n and  k k. Let  f(i)=ik f(i)=ik, please evaluate the sum  f(1)+f(2)+...+f(n) f(1)+f(2)+...+f(n). The problem is simple as it looks, apart from the value of  n nin this question is quite large.  Can you figure the answer out? Since the answer may be too large, please output the answer modulo  109+7 109+7. Input The first line of the input contains an integer  T(1T20) T(1≤T≤20), denoting the number of test cases.  Each of the following  T T lines contains two integers  n(1n10000) n(1≤n≤10000) and  k(0k5) k(0≤k≤5).  Output For each test case, print a single line containing an integer modulo  109+7 109+7. Sample Input 3 2 5 4 2 4 1 Sample Output 33 30

10

这个题的数据量是很大的,因此每求一次a^b,都要进行取模,所以我们把pow()函数在这儿重新写 一次,同时,最后的输出结果也要取模。

#include <iostream> #include<cstdio> #include<cmath> using namespace std; const int N=1000000000+7; long long pow1(int a,int b) { long long p=1; for(int i=1;i<=b;i++) { p*=a; p%=N; } return p; } int main() { int T; scanf("%d",&T); while(T--) { long long a,b,sum=0; scanf("%lld%lld",&a,&b); for(int i=1;i<=a;i++) sum+=pow1(i,b); printf("%lld\n",sum%N); } return 0; }

转载请注明原文地址: https://www.6miu.com/read-1150319.html

最新回复(0)