取模运算
关于母亲的诗句-
取模运算
取模运算即模运算
模运算即求余运算。
“
模
”
是
“
< br>Mod
”
的音译，
模运算多应用
于程序编写中。
Mod
的含义为求余。
模运算在数论和程序设计中都有着广泛的应用，
从奇偶数的判别到素数的判别，从模幂运算到最大公约数的求法，从孙子问题到凯撒
< br>密码问题，
无不充斥着模运算的身影。
虽然很多数论教材
上对模运算都有一定的介绍，
但多数都是以纯理论为主，对于模运算在程序设计中的应用
涉及不多。
例如
11
Mod
2
，值为
1
上述模运算多用于程序编写，举一例来说明模运算的原理：
Turbo Pascal
对
mod<
/p>
的解释是这样的：
A Mod B=A-(A
div B) * B
（
div
含义
为整除）
运算及其应用
本文以
c
++
语言为载体，
对基本的模运算应用进行了分析和程序设计，
以理论和实
际相结合的方法向大家介绍模运算的基本应用。
。
一
基本理论：
基本概念：
给定一个正整数
< br>p
，任意一个整数
n
，一定存在
等式
n = kp + r
；
其中
k
、<
/p>
r
是整数，且
0 ≤ r < p
，称呼
k
为
n
除以
p
的商，
r
为
n
除以
p
的余数。
对于正
整数
p
和整数
a,b
< br>，定义如下运算：
取模运算：
a %
p
（或
a mod p
）
，表示
a
除以
p
的余数。
模
p
加法：
(a + b) % p
，其结果是
a+b
算术和除以
p
的余数，也就是说
，
(a+b) = kp
+r
，
则
(a + b) % p =
r
。
模
p
减法：
(a-b) % p
，其结果是
a-
b
算术差除以
p
的余数。
< br>模
p
乘法：
(a * b) %
p
，其结果是
a * b
算术乘法除以
p
的余数。
说明：
1.
同余式：
正整数
a
，
b
对
p
取模，它们的余数相同，记做
a
≡ b % p
或者
a ≡ b (mod
p)
。
2. n % p
得到结果的正负由
被除数
n
决定
,
与
p
无关。
例
如
：
7%4
=
3
，
-7%4
=
-3
，
7%-4
=
3
，
-7%-4
=
-3
。
基本性质：
（
1
）若<
/p>
p|(a-b)
，则
a≡b (%
p)
。例如
11 ≡ 4 (%
7)
，
18 ≡ 4(% 7)
（
2
）
(a
% p)=(b % p)
意味
a≡b (% p)
（
3
）对称性：
a≡b (%
p)
等价于
b≡a (% p)
（
4
）传递性：若
a≡b (%
p)
且
b≡c (% p)
，则
a≡c (% p)
运算规则：
模运算与基本四则运算有些相似，但是除法例外。其规则如下：
(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
）
ab
% 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
）
若
a≡b (%
p)
，则对于任意的
c
，都有
ac
≡ bc (%p)
；
（
13
）
二
基本应用：
1.
判别奇偶数
奇偶数
的判别是模运算最基本的应用，也非常简单。易知一个整数
n
对
2
取模，如果余
数为
< br>0
，则表示
n
为偶数，否则
n
为奇数。
C++
实现功能函数：
/*
函数名：
IsEven
函数功能：判别整数
n
的奇偶性。能被
2
整除为
偶数，否则为奇数
输入值：
int
n
，整数
n
返回值：
bool
，若整数
n
是偶数，返回
true
，否则返回
false
*/
bool IsEven(int n)
{
return (n % 2
== 0);
}
2.
判别素数
一个数
，如果只有
1
和它本身两个因数，这样的数叫做质数（或素数）
。例如
2
，
3
，
5
，
7
是质数，而
4
，
6
，
8<
/p>
，
9
则不是，后者称为合成数或合数。
判断某个自然数是否是素数最常用
的方法就是试除法：
用比该自然数的平方根小的正整
数去除这个
自然数，若该自然数能被整除，则说明其非素数。
C++
实现功能函数：
/*
函数名：
IsPrime
函数功能：判别自然数
n
是否为素数。
输入值：
int
n
，自然数
n
返回值：
bool
，若自然数
n
是素数，返回<
/p>
true
，否则返回
false
*/
bool IsPrime(unsigned int n)
{
unsigned maxFactor = sqrt(n);
//n
的最大因子
for (unsigned
int i=2; i<=maxFactor; i++)
{
if (n % i == 0)
//n
能被
i
整除，则说明
n
非素数
{
return false;
}
}
return true;
}
3.
最大公约数
求最大公约数最常见的方法是欧几
里德算法（又称辗转相除法）
，其计算原理依赖于定
理：
gcd(a,b) = gcd(b,a mod b)
证明：
a
可以表示成
a = kb +
r
，则
r = a mod b
假设
d<
/p>
是
a,b
的一个公约数，则有
d|a, d|b
，而
r = a -
kb
，因此
d|r
因此
d<
/p>
是
(b,a mod
b)
的公约数
假设
d
是
(b,a mod
b)
的公约数，则
d | b , d |r
，但是
a = kb +r
因此
d<
/p>
也是
(a,b)
的公约数
因此
(a,b)
和
(b,a
mod
b)
的公约数是一样的，其最大公约数也必然相等，得证。
C++
实现功能函数：
/*
函数功能：
利用欧几里德算法，采用递归方式，求两个自然数的最大公约数
函数名：
Gcd
输入值：
unsigned int
a
，自然数
a
unsigned int
b
，自然数
b
返回值：
unsigned
int
，两个自然数的最大公约数
*/
unsigned int
Gcd(unsigned int a, unsigned int b)
{
if (b == 0)
return a;
return Gcd(b, a % b);
}
/*
函数功能：
利用欧几里德算法，采用迭代方式，求两个自然数的最大公约数
函数名：
Gcd
输入值：
unsigned int
a
，自然数
a
unsigned int
b
，自然数
b
返回值：
unsigned
int
，两个自然数的最大公约数
*/
unsigned int
Gcd(unsigned int a, unsigned int b)
{
unsigned int
temp;
while (b != 0)
{
temp = a % b;
a = b;
b =
temp;
}
return a;
}
4
．模幂运算
利用模
运算的运算规则，我们可以使某些计算得到简化。例如，我们想知道
3333^5555
的末位是什么。很明显不可能直接把
3333^5555
的结果计算出来，那样太大了。但我们想要
确定的是
< br>3333^5555
（
%10
）
，所以问题就简化了。
根据运算规则
（
4
）
ab % p = ((a
% p)b) % p
，
我们知道
3
333^5555
（
%10
）
= 3^5555
（
%10
）
。
由于
3^4 = 81
，所以
3^4
（
%1
0
）
= 1
。
根据运
算规则（
3
）
(a * b) % p = (a % p * b % p) % p
，由于
5555 = 4 * 1388 + 3
，我们
得到
3^5555
（
%10
）
=
（
3^(4*1388) * 3^3
）
（
%10
）
=
（
（
3^(4*1388)
（
%10
）
* 3^3
（
%10
）
）
（
%10
）
=
（
1 *
7
）
（
%10
）
= 7
。
计算完毕。
利用这些规则我们可以有效地计算
X^N(% P)
。简单的算法是将
result
初始化为
1
，然后
重复将
res
ult
乘以
X
，每次乘法之后应用
%
运算符（这样使得
result
的值变小，以免溢出）
，
执行
< br>N
次相乘后，
result
就是
我们要找的答案。
这样对于较小的
N
< br>值来说，
实现是合理的，
但是当
N
的值很大时，
需要计算很长时间，
是
不切实际的。
下面的结论可以得到一种更好的算法。
如果<
/p>
N
是偶数，那么
X^N =
（
X*X
）
^[N/2]<
/p>
；