p次方求和

Time Limit:1000MS  Memory Limit:65536K

Total Submit:196 Accepted:46

Description

一个很简单的问题，求1^p+2^p+3^p+……+n^p的和。

Input

第一行单独一个数字t表示测试数据组数。接下来会有t行数字，每行包括两个数字n,p， 

输入保证0< n< =1000,0< =p< =1000。

Output

输出1^p+2^p+3^p+……+n^p对10003取余的结果，每个结果单独占一行。

Sample Input

2

10 1

10 2

Sample Output

55

385

Source

[Submit]  
[Go Back]   [Status]  
[Discuss]

#include <stdio.h>

int a[1002][1002];

int main()

{

	int i, j, s, n, p, t;

	for ( i=1; i<1002; i++ ) {

		a[i][0] = 1;

	}

	for ( j=1; j<1002; j++ ) {

		for ( i=1; i<1002; i++ ) {

			a[i][j] = a[i][j-1] * i % 10003;//构造次方表，a[i][j]表示i的j次方

		}

	}

	scanf("%d", &t);

	while ( t-- )

	{

		s = 0;

		scanf("%d%d", &n, &p);

		for ( i=1; i<=n; i++ ) {

			s = s + a[i][p];

		}

		printf("%d\n", s % 10003);

	}

	return 0;

}