POJ 1995 Raising Modulo Numbers 题解 《挑战程序设计竞赛》

POJ 1995 Raising Modulo Numbers

我爱算模：有的人爱看片儿、有的人爱在地窖里造原子弹、有的人爱用Windows，我爱计算(A₁^B₁+A₂^B₂+ … +A_H^B_H)mod M

2.6 数学问题的解题窍门

快速幂运算

水题，熟悉模运算的运算规则即可：

运算规则

模运算与基本四则运算有些相似，但是除法例外。其规则如下：

(a + b) % p = (a % p + b % p) % p （1）

(a – b) % p = (a % p – b % p) % p （2）

(a * b) % p = (a % p * b % p) % p （3）

(a^b) % p = ((a % p)^b) % p （4）

结合律：

((a+b) % p + c) % p = (a + (b+c) % p) % p （5）

((a*b) % p * c)% p = (a * (b*c) % p) % p （6）

交换律：

(a + b) % p = (b+a) % p （7）

(a * b) % p = (b * a) % p （8）

分配律：

((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p （9）

重要定理：

若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)；（10）

若a≡b (% p)，则对于任意的c，都有(a * c) ≡ (b * c) (%p)；（11）

若a≡b (% p)，c≡d (% p)，则 (a + c) ≡ (b + d) (%p)，(a – c) ≡ (b – d) (%p)，

(a * c) ≡ (b * d) (%p)，(a / c) ≡ (b / d) (%p)； （12）

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
using namespace std;

typedef long long LL;

// return (a * b) % m
LL mod_mult(LL a, LL b, LL m)
{
	LL res = 0;
	LL exp = a % m;
	while (b)
	{
		if (b & 1)
		{
			res += exp;
			if (res > m) res -= m;
		}
		exp <<= 1;
		if (exp > m) exp -= m;
		b >>= 1;
	}
	return res;
}

// return (a ^ b) % m
LL mod_exp(LL a, LL b, LL m) {
	LL res = 1;
	LL exp = a % m;
	while (b)
	{
		if (b & 1) res = mod_mult(res, exp, m);
		exp = mod_mult(exp, exp, m);
		b >>= 1;
	}
	return res;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int Z;
	cin >> Z;
	while (Z--)
	{
		int M, H;
		cin >> M >> H;
		int ans = 0;
		while (H--)
		{
			int A_i, B_i;
			cin >> A_i >> B_i;
			ans += mod_exp(A_i, B_i, M);
		}
		ans %= M;
		cout << ans << endl;
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 1995 Raising Modulo Numbers 题解 《挑战程序设计竞赛》