1995-Raising Modulo Numbers

問題（外部リンク）

1995 -- Raising Modulo Numbers

実装の概要

問題文ではやや難しい表現を使っていますが、出力の仕様に書いてある計算式の通り累乗したものを加算してmodを求めることで解くことができます。
その際、指数部が大きく普通にループを回すと計算が間に合わないので繰り返し二乗法を用います。
Mの値がそれほど大きくないので数回足したくらいではオーバーフローにはなりませんが、途中でmodを計算しても同じ結果になるのでその都度modを求めた方が安全です。

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int z = Integer.parseInt(br.readLine());

		for(int i = 0; i < z; i++){
			int m = Integer.parseInt(br.readLine());
			int h = Integer.parseInt(br.readLine());

			int result = 0;
			for(int j = 0; j < h ; j++){
				String[] tmpArray = br.readLine().split(" ");

				int a = Integer.parseInt(tmpArray[0]);
				int b = Integer.parseInt(tmpArray[1]);

				result += repeatablePow(a, b, m);
				result %= m;
			}

			System.out.println(result);
		}
	}

	static long repeatablePow(int x, int n, int mod){
		if(n == 0){
			return 1;
		}
		long result = repeatablePow((int)((long)x*x%mod), n/2, mod);
		if(n % 2 == 1){
			result = result*x%mod;
		}
		return result;
	}

}