学步园

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=420

超时了一次，最后用二分求幂才AC

/*import java.math.BigInteger;
import java.util.Scanner;
public class Main{//超时
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		int N=input.nextInt();
		while(N-->0){
			int n=input.nextInt();
			int p=input.nextInt();
			long begin=System.currentTimeMillis();
			BigInteger sum=BigInteger.valueOf(1);
			for(int i=2;i<=n;i++){
				sum=sum.add(BigInteger.valueOf(i).pow(p).mod(BigInteger.valueOf(1003)));
			}
			System.out.println(sum);
			System.out.println(System.currentTimeMillis()-begin);
		}
	}
}*/

AC代码：

import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		int N=input.nextInt();
		while(N-->0){
			int n=input.nextInt();
			int p=input.nextInt();
			if(p==0){
				System.out.println(n);
				continue;
			}
			long sum=0;
			for(int i=1;i<=n;i++){
				sum=(sum+pow(i,p)%10003)%10003;
			}
			System.out.println(sum);
		}
	}

	private static long pow(int a, int b) {//二分求幂
		// TODO Auto-generated method stub
		if(b==1)
			return a;
		long x=pow(a,b/2);
		long v=((x%10003)*(x%100003))%10003;
		if(b%2==1)
			v=v*a%10003;
		return v;
	}
}