NYOJ 420 p次方求和 大数的幂

2
10 1
10 2

55
385

    这个题求n的p次方是个难点，因为p会取到1000，平常求幂次方的求法肯定是不行的，所以就要优化。最简单的优化方法就是用二进制优化，具体怎样不在详细说明，百度一下，你就知道。

#include<stdio.h>
#include<math.h>
long long  fun(int  a,int b) //求a的b次方
{
 long long s=1;
 while(b!=0)
 {
     if(b&1) //b%2==1
      s=s*a%10003;
     a=a*a%10003;
     b>>=1;
 }
 return s;
}
int main()
{
    int  t,n,p,i;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&p);
        if(n==1)
        {
            printf("1n");
            continue;
        }
        else if(n==0)
        {
            printf("0n");
            continue;
        }
        else if(p==0)
        {
            printf("%dn",n);
            continue;
        }
        else
        {
          long long sum=1; //因为1的任何次幂都是1，所以直接令sum=1，节省时间
          for(i=2;i<=n;i++)
            sum+=fun(i,p);
          printf("%lldn",sum%10003);
        }
    }
    return 0;
}