放牧代码和思想
专注自然语言处理、机器学习算法
    恕不接待索要源码语料者、索求技术方案者、以及不Google的懒人。

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

目录

POJ 1995 Raising Modulo Numbers

我爱算模:有的人爱看片儿、有的人爱在地窖里造原子弹、有的人爱用Windows,我爱计算(A1B1+A2B2+ … +AHBH)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 题解 《挑战程序设计竞赛》

分享到:更多 ()

评论 1

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    翻译666

    哈哈2年前 (2016-07-23)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机