1842.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1842 on 2006-02-17 at 20:06:10 */ 
#include <cstdio>

int modular_exp(int, int, int);

int main()
{
	int i, t, T, m, n;
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d %d", &m, &n);
		int mod = 0;
		for(i = 0; i < n; i++) {
			int a, b;
			scanf("%d %d", &a, &b);
			mod += modular_exp(a%m, b, m);
		}
		printf("%d\n", mod%m);
	}
	
	return 0;
}

int modular_exp(int a, int b, int n)
{
	int d = 1, bin[32], num, i; 

	for(num = 0; b != 0; num++) {
		bin[num] = b & 1;
		b >>= 1;
	}
	for(i = num-1; i >= 0; i--) {
		d = d * d % n;
		if(bin[i] == 1) d = d * a % n;
	}

	return d;
}