-
取模运算
取模运算即模运算
模运算即求余运算。
“
模
”
是
“
< br>Mod
”
的音译,
模运算多应用
于程序编写中。
Mod
的含义为求余。
模运算在数论和程序设计中都有着广泛的应用,
从奇偶数的判别到素数的判别,从模幂运算到最大公约数的求法,从孙子问题到凯撒
< br>密码问题,
无不充斥着模运算的身影。
虽然很多数论教材
上对模运算都有一定的介绍,
但多数都是以纯理论为主,对于模运算在程序设计中的应用
涉及不多。
例如
11
Mod
2
,值为
1
上述模运算多用于程序编写,举一例来说明模运算的原理:
Turbo Pascal
对
mod<
/p>
的解释是这样的:
A Mod B=A-(A
div B) * B
(
div
含义
为整除)
运算及其应用
本文以
c
++
语言为载体,
对基本的模运算应用进行了分析和程序设计,
以理论和实
际相结合的方法向大家介绍模运算的基本应用。
p>
。
一
基本理论:
基本概念:
给定一个正整数
< 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)
(
p>
3
)对称性:
a≡b (%
p)
等价于
b≡a (% p)
(
4
p>
)传递性:若
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
为偶数,否则
p>
n
为奇数。
C++
实现功能函数:
/*
函数名:
IsEven
函数功能:判别整数
n
的奇偶性。能被
2
整除为
偶数,否则为奇数
输入值:
int
n
,整数
n
返回值:
bool
,若整数
n
是偶数,返回
p>
true
,否则返回
false
*/
bool IsEven(int n)
{
return (n % 2
== 0);
}
2.
判别素数
一个数
,如果只有
1
和它本身两个因数,这样的数叫做质数(或素数)
。例如
2
,
3
,
5
,
p>
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
,每次乘法之后应用
p>
%
运算符(这样使得
result
的值变小,以免溢出)
,
执行
< br>N
次相乘后,
result
就是
我们要找的答案。
这样对于较小的
N
< br>值来说,
实现是合理的,
但是当
N
的值很大时,
需要计算很长时间,
是
不切实际的。
下面的结论可以得到一种更好的算法。
如果<
/p>
N
是偶数,那么
X^N =
(
X*X
)
^[N/2]<
/p>
;
-
-
-
-
-
-
-
-
-
上一篇:2020人文英语4-形考unit2单元自测-
下一篇:模运算