二 基本应用:
1.判别奇偶数
奇偶数的判别是模运算最基本的应用,也非常简单。易知一个整数n对2取模,如果余数为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,9 则不是,后者称为合成数或合数。
判断某个自然数是否是素数最常用的方法就是试除法:用比该自然数的平方根小的正整数去除这个自然数,若该自然数能被整除,则说明其非素数。
C++实现功能函数:
/*
函数名:IsPrime
函数功能:判别自然数n是否为素数。
输入值:int n,自然数n
返回值:bool,若自然数n是素数,返回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是a,b的一个公约数,则有d|a, d|b,而r = a - kb,因此d|r
因此d是(b,a mod b)的公约数
假设d 是(b,a mod b)的公约数,则d | b , d |r ,但是a = kb +r
因此d也是(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的结果计算出来,那样太大了。但我们想要确定的是3333^5555(%10),所以问题就简化了。
根据运算规则(4)ab % p = ((a % p)b) % p ,我们知道3333^5555(%10)= 3^5555(%10)。由于3^4 = 81,所以3^4(%10)= 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,然后重复将result乘以X,每次乘法之后应用%运算符(这样使得result的值变小,以免溢出),执行N次相乘后,result就是我们要找的答案。
这样对于较小的N值来说,实现是合理的,但是当N的值很大时,需要计算很长时间,是不切实际的。下面的结论可以得到一种更好的算法。
如果N是偶数,那么X^N =(X*X)^[N/2];
如果N是奇数,那么X^N = X*X^(N-1) = X *(X*X)^[N/2];
其中[N]是指小于或等于N的最大整数。
C++实现功能函数:
/*
函数功能:利用模运算规则,采用递归方式,计算X^N(% P)
函数名:PowerMod
输入值:unsigned int x,底数x
unsigned int n,指数n
unsigned int p,模p
返回值:unsigned int,X^N(% P)的结果
*/
unsigned int PowerMod(unsigned int x, unsigned int n, unsigned int p)
{
if (n == 0)
{
return 1;
}
unsigned int temp = PowerMod((x * x)%p, n/2, p); //递归计算(X*X)^[N/2]
if ((n & 1) != 0) //判断n的奇偶性
{
temp = (temp * x) % p;
}
return temp;
}