POJ-1995 Raising Modulo Numbers 题解

题目大意

有t组数据，每组输入h和m，有h组a，b，计算出$ (A_1^{B_1}+A_2^{B_2}+ … +A_H^{B_H})mod M $的结果。

解题思路

没什么好说的，标准的快速幂模板题。

（不熟。。

完整代码

#include <iostream>
using namespace std;

int m;
long long qpow(int a,int b) {//快速幂
	long long t = 1;
	while (b) {
		if (b & 1)
			t= (t*a)%m;
		a = (a * a) % m;
		b >>= 1;
	}
	return t;
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		int h;
		cin >> m >> h;
		long long ans = 0;
		for (int i = 1; i <= h; i++) {
			int a, b;
			cin >> a >> b;
			long long t = 1;
			t = qpow(a%m, b);
			ans += (t) % m;
			ans %= m;
		}		
		cout << ans << endl;
	}
}