NYOJ 420 P次方求和

p次方求和

描述

一個很簡單的問題，求1^p+2^p+3^p+……+n^p的和。

輸入

第一行單獨一個數字t表示測試數據組數。接下來會有t行數字，每行包括兩個數字n,p，
輸入保證0

輸出

輸出1^p+2^p+3^p+……+n^p對10003取余的結果，每個結果單獨占一行。

樣例輸入

2
10 1
10 2

樣例輸出

55
385

AC碼：

#include
#define N 10003
int main()
{
	long long T,n,p,i,b,t,a,sum;  // 必須用long long
	scanf("%d",&T);
	while(T--)
	{
		scanf("%lld%lld",&n,&p);
		if(n==0)     // md，坑爹，題目明明n是大於0的
		{            //    但沒有這個條件，就是不通過!!!
			printf("0\n");
			continue;
		}
		sum=1;
		for(i=2;i<=n;i++)
		{
			a=i;
			b=p;
			t=1;
			while(b)
			{
				if(b&1)
					t=(t*a)%N;
				a=(a*a)%N;
				b=b/2;
			}
			sum=(sum+t)%N;
		}
		printf("%d\n",sum);
	}
	return 0;
}