Easy Summation

你的名字 2022-05-13 12:28 164阅读 0赞

Problem Description  
You are encountered with a traditional problem concerning the sums of powers.  
Given two integers n and k. Let f(i)=ik, 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 109+7.

Input  
The first line of the input contains an integer T(1≤T≤20), denoting the number of test cases.  
Each of the following T lines contains two integers n(1≤n≤10000) and k(0≤k≤5).

Output  
For each test case, print a single line containing an integer modulo 109+7.

Sample Input  
3  
2 5  
4 2  
4 1

Sample Output  
33  
30  
10  
分析：  
主要是练习二分求幂哈 另外单纯的二分求幂的题目很少 都是带取模什么的

//二分求幂
    int pow(int a,int n)
    {
        int result=1;
        while(n!=0)
        {
            if(n%2==1)
            result=result*a%N;
            n=n/2;
            a=a*a%N;
        }
        return result;
    }

代码总览：

#include <cstdio>
    #include <iostream>
    #include <cstring>
    using namespace std;
    #define N 1000000007
    int poww(long long a,long long n)
    {
        int result=1;
        while(n!=0)
        {
            if(n%2==1)
            result=result*a%N;
            n=n/2;
            a=a*a%N;
        }
        return result;
    }
    int main()
    {
        long long t,a,b;
        scanf("%lld",&t);
        while(t--)
        {
          long long sum=0;
          scanf("%lld %lld",&a,&b);
          for(long long i=1;i<=a;i++)
          {
            sum+=poww(i,b);
            sum=sum%N;
           }
           printf("%lld\n",sum);    
        }
        return 0;
    }   
    //这里都定义为long long类型 避免出错