首页 > 代码库 > 模运算

模运算

【模运算的定义及概念】

模运算即求余运算。“模”是“Mod”的音译,模运算多应用于程序编写中。 Mod的含义为求余。模运算在数论和程序设计中都有着广泛的应用,从奇偶数的判别到素数的判别,从模幂运算到最大公约数的求法,从孙子问题到凯撒密码问题,无不充斥着模运算的身影。

【基本理论】 

  给定一个正整数p,任意一个整数n,一定存在等式 n = kp + r ; 
  其中k、r是整数,且 0 ≤ r < p,称呼k为n除以p的商,r为n除以p的余数。 
  对于正整数p和整数a,b,定义如下运算: 
  取模运算: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的余数。 
  模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|(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) 

【运算规则】

模运算与基本四则运算有些相似,但是除法例外。其规则如下: 
  (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) % p  
  (4)(a^b) % p = ((a % p)^b) % p  
  (5)结合率: ((a+b) % p + c) % p = (a + (b+c) % p) % p  
  (6)((a*b) % p * c)% p = (a * (b*c) % p) % p  
  (7)交换率: (a + b) % p = (b+a) % p  
  (8)(a * b) % p = (b * a) % p  
  (9)分配率: ((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p  
  (10)重要定理:若a≡b (% p),则对于任意的c,都有(a + c) ≡ (b + c) (%p); 
  (11)若a≡b (% p),则对于任意的c,都有(a * c) ≡ (b * c) (%p); 
  (12)若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);  
  (13)若a≡b (% p),则对于任意的c,都有ac≡ bc (%p);

基本应用】

1.判断素数

2.求最大公约数利用gcd(a,b)=gcd(b,a mod b);(欧几里得算法与扩展欧几里得算法)

3.模幂运算

利用模运算的运算规则,我们可以使某些计算得到简化。例如,我们想知道3333^5555的末位是什么。很明显不可能直接把3333^5555的结果计算出来,那样太大了。但我们想要确定的是3333^5555(%10),所以问题就简化了。

根据运算规则(4)a^b% 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。

下面的结论可以得到一种更好的算法: 
  如果N是偶数,那么X^N =(X*X)^[N/2]; 
  如果N是奇数,那么X^N = X*X^(N-1) = X *(X*X)^[N/2]; 
  其中[N]是指小于或等于N的最大整数。 
 下面我写出这一算法的代码:

 

 1 int PowerMod( int x, int n, int p) 2 { 3     if(n==0) 4     return 1; 5     else 6     int cmp=PowerMod((x*x)%p,n/2,p);//递归调用 7     if(n&1!=0)//如果是奇数则多乘以一个x 8     cmp=(cmp*x)%p; 9     return cmp;10 }

 

4.中国剩余定理

中国剩余定理可以描述为:

若某数x分别被d1、、…、dn除得的余数为r1、r2、…、rn,则可表示为下式:
x=R1r1+R2r2+…+Rnrn+RD   其中R1是d2、d3、…、dn的公倍数,而且被d1除后余数为1;(称为R1相对于d1的数论倒数)

R2 是d1,d3,d4,······dn的公倍数,而且被d2除后余数为1;

…  

Rn是d1、d2、…、dn-1的公倍数,而且被dn除,余数为1;
D是d1、d2、…、dn的最小公倍数;R是任意整数(代表倍数),可根据实际需要决定;
且d1、、…、dn必须互质,以保证每个Ri(i=1,2,…,n)都能求得.

(注:因为R1对d1求余为1,所以R1r1对d1求余为r1,这就是为什么是R1对d1求余为1的目的,其次,R2r2,R3r3…Rnrn对d1求余都是0)

对于中国剩余定理有个简单理解并记忆的方法:

中国剩余定理的思想在于先找到一个满足条件的数,不管是不是最小的,如果不是最小的就不断减公倍数,中国剩余定理的巧妙在于把满足条件的数分成三个部分相加。

例如:
假设满足条件的数为:M=3*5*a+5*7*b+3*7*c
先让它满足条件1:除以3余1,我们看M的第一部分和第三部分能被3整除,只要第二部分除以3余1就行了,选择b=2就满足
再满足条件2:除以5余2,考虑第三部分就行了,选择c=2就满足
最后满足条件3:除以7余3,考虑第一部分就行了,选择a=3
这样M=3*5*3+5*7*2+3*7*2=157,比公倍数大,减去公倍数,157-105=52是满足条件最小数

以我个人理解写成下面这个形式(以3个数为例)

X被a,b,c处分别余r1,r2,r3。表示为:

X%a = r1                     x%b = r2                     x%c = r3

bc*k1 % a = 1     ac*k3 % b = 1     ab*k3 % c = 1

所以

x = bc * k1 * r1 + ac * k2 * r2 + ab * k3 * r3

 下面我贴出代码:

 1 int PowerMod( int d1, int d2, int d3,int s1,int s2,int s3)//d1,d2,d3是三个除数 2 { 3     int r1=d2*d3,r2=d1*d3,r3=d1*d2; 4     for(int i=1;1;i++) 5     if((r1*i)%d1==1) 6     { 7         r1=r1*i; 8         break; 9     }10     for(int j=1;1;j++)11         if((r2*j)%d2==1)12         {13             r2=r2*j;14             break;15         }16     for(int z=1;1;z++)17     if((r3*z)%d3==1)18     {19         r3=r3*z;20         break;21     }22     cout<<r1<< <<r2<< <<r3<<endl;23     int left=(r1*s1+r2*s2+r3*s3)%LCM(r1,r2,r3);//所求数字的最小值24     return left;25 }