(Relax 快速幂取模1.3)POJ 1995 Raising Modulo Numbers(快速幂取模模板题+同余模公式)

同余模公式：

(a+b)%m=(a%m+b%m)%m

(a*b)%m=(a%m*b%m)%m

/*
 * POJ_1995.cpp
 *
 *  Created on: 2013年11月19日
 *      Author: Administrator
 */
#include 
  
   
#include 
   
     using namespace std; typedef long long ll; /** * 快速幂取模 * 求a^b%m的值 */ ll qpow(ll a, ll b, ll m) { ll ans = 1; while (b) { if (b & 1) { ans *= a; ans %= m; } a *= a; a %= m; b >>= 1; } return ans; } int main() { int z; scanf("%d", &z); while (z--) { ll m, h; scanf("%lld%lld", &m, &h); ll ans = 0; while (h--) { ll a, b; scanf("%lld%lld", &a, &b); ans += qpow(a, b, m);//这里应用到了同余模公式:(a+b)%m=(a%m+b%m)%m ans %= m; } printf("%lld\n", ans); } return 0; }