关于数论——同余、逆元、中国剩余定理、Lucas定理等

数学是科学的女王,而数论是数学的女王。——高斯

数论是近年ACM竞赛中频繁出现的一类问题,我在队里负责数论的一部分知识讲解,最近几天对其进行了大力学习。其实刨根问底,数论在ACM中的题型基本是应用题,或者是在某一步的数据处理时需要用到某个定理来缩小结果,减少运算量等等。很少有裸题,所以在掌握定理之后,一定要学会灵活运用。

数论是一门研究整数的理论,同时也就是数论方面的题型不会涉及到浮点数double、float的精度问题。在整数的除法领域,没有小数点,只有余数。

同余

那我们就从这里讲起。首先介绍一个基本概念,同余。我们之前学过除法运算,学过取模运算。而在数论中,比较重要且基础的一种运算是同余运算。

≡ 

同余是数论中的一种等价关系,同余式的基本形式为 a  ≡  b(mod  m),即a与b关于m同余。表示a和b除以m的余数相等。还有一种解释是a减b的结果可以整整除m,而求解同余式中的未知数的式子,当然就是同余方程。

然后我们介绍一下同余的性质。同余大体来讲有五个性质:

  1. 自反性。即 a  ≡  a   (mod m)
  2. 对称性。即 a  ≡  b(mod m)<=> b  ≡  a(mod  m)
  3. 传递性。若 a  ≡  b   (mod m),b  ≡  c   (mod m),则a  ≡  c   (mod m)
  4. 可加性。同余式相加 若a≡b (mod m),c≡d(mod m),则a  c ≡ b  d (mod m),这个如果要证明的话,其实每个数都是可以拆成两部分的,即m*(a/m)+ (a%m)。将这个形式带入,很容易得到该结论。
  5. 可乘性。同余式相乘 若a  ≡  b  (mod m),c  ≡  d  (mod m),则ac  ≡  bd   (mod m)。同样,将上面的形式带入也很容易证明。

 

逆元

接下来介绍逆元。逆元又叫数论倒数,是与同余有关的基本概念,是一个可以取消另一给定元素运算的元素。如果两个数a和b,它们的乘积关于模m余1,我们称它们互为关于模m的数论倒数。一般形式为:a *b≡ 1(mod m)。还有一种形式是:amax1(mod  m)xam而我们要处理的一个大问题,就是如何去求逆元。

有的题目要求结果mod一个大质数,如果原本的结果中有除法,比如除以a,那就可以乘以a的逆元替代。接下来要介绍的其他几个算法,也多多少少用到了逆元。

下面介绍两种求逆元的方法。

 

欧拉函数(费马小定理求逆元)

φ:N→N,n→φ(n)称为欧拉函数。对正整数n,欧拉函数的值是少于或等于n的数中与n互质的数的数目。

关于欧拉定理的相关性质大家可以到这个链接进行查看:ACdreamer的博客,由于一些性质今天并不会用到,所以不再赘述,感兴趣的同学可以前去查看。

此外有欧拉定理:设a,m∈N,(a,m)=1(即a与m互质,最大公约数为1),则aφ(m)≡1(mod m),根据上边的性质我们可以了解到。当p为质数时,欧拉函数的值为p-1。由此可得欧拉定理的一个特殊情况。

a(p-1) ≡ 1(mod p)

(p为质数且a与p互质)

这就是大名鼎鼎的费马小定理。它是欧拉定理的一个特殊情况,我们观察这个式子,是不是有些似曾相识?没错,将式子稍微变形,我们就可以得到

a*a(p-2) ≡ 1(mod p)

也就是说,a关于p的逆元正是a(p-2)。于是,当a与p互质时,我们仅需使用快速幂求出a(p-2)的值即可。时间复杂度O(√n)。要求:a和p互素且p为素数。

代码:

 

拓展欧几里得求逆元

拓展欧几里得算法可以求出ax+by=gcd(a,b)=d的整数解。那利用拓展欧几里得算法如何求乘法逆元呢?很简单,我们对逆元的方程做一个简单的变换。

ax1(mod  m) <=>a*x+m*y=1

这里我们可以看到,当gcd(a,m)不为1的时候,方程是无解的。也就是说我们只需求出一个x的解,即可得出a的逆元。但题目往往要求我们求最小的逆元,非常简单,直接让x%m即可。时间复杂度O(loga),要求互素(m不一定要是素数)。

代码:

 

线性处理1~n的逆元

刚刚的两种方法全部要求a和m需要互质,但是有的题目两个数并不互质,这时我们有一种不需要a和m互质的算法(但依然要求m为质数),线性处理法。

先说结论,这个算法可以去求1,2,3,…,N关于m的逆元(m为质数),x-1−(y/x)*(mod x)-1(mod y)

下面我们来证明这个结论。

假设y=ax+b, b<i, 1<x<y ,并将这个式子放在(mod y) 

a≡ 0 (mod y)

两边同时乘上x-1b-1得到

ab-1 x-1 ≡ (mod y)
x-1 ≡ ab-1 (mod y)

再将⋅ x  b 代入得到

x-1 − ⌊ y /⌋ ⋅ mod )-1  mod )
这样通过迭代我们可以得到从1~n的所有逆元,复杂度o(n).
代码如下:

 

中国剩余定理

介绍完同余和逆元之后,我们来看一些应用的算法。

中国剩余定理,又称孙子定理。用于解决一元线性同余方程组问题。

一元线性同余方程组问题最早可见于中国南北朝时期(公元5世纪)的数学著作《孙子算经》卷下第二十六题,叫做“物不知数”问题,原文如下:

有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?

用现代数学公式来表达这段话的含义:

x  ≡  2(mod  3)

x  ≡  3(mod  5)

x  ≡  2(mod  7)

求解x

先说结论,这个方程组的解为

 x = 5 * 7 * 1+ 3 * 7 * 3 +3 * 5 * 2 + 105 * K ( K ⊆ Z)

x = 128 + 105 * K ( K ⊆ Z )

先来验证一下,在x解的第一种形式中,我们把它拆成了四个部分,我们可以观察一下。第一个部分对应x  ≡  2(mod  3),有5*7,即在mod 5和 mod 7的运算中为零,同时可以看到它 mod 3余2,能够满足方程组里的每一个方程。接下来的几个部分同理,而最后一部分105则是3*5*7的结果,我们无论如何加减这个部分,结果都能让它满足三个方程,因为105 mod每一个除数都是0。

现在我们来看看这个式子是如何被求出来的。我们先把方程抽象为

x  ≡  r1(mod  m1)
x  ≡  r2(mod m2)

·

·

 x  ≡  rn(mod  mn)

(n为下标)

我们已经知道,每个式子所对应的解的一部分要能够整除其他的式子的除数部分m,并且要能够模自己的余数的时候结果等于自己的r。显然,这部分是要等于除了自己的所有m的乘积的某个倍数,同时这个结果除以自己的m还要等于r。

我们的任务就是去构造这个解。我们先设M=m1*m2*……*mn,Mn=M/mn。即Mi是除了mi以外的n-1个整数的乘积,设ti为Mi模mi的数论倒数(乘法逆元)。

讲到这里你可能已经明白了。我们的Mn就是刚刚说到的所有乘积,我们要将它乘以一个倍数,使得这个结果模mn的解为rn。

那为什么需要Mi的乘法逆元呢?

很简单,哪个数字模mn永远等于rn呢,当然是rn本身,我们先让Mi乘以rn,在去乘以Mi的逆元,Mi*ti ≡  1(mod  mn),根据同余的可乘性,rn  ≡  rn(mod  mn),两式相乘,得到Mi*ti*rn ≡  rn(mod  mn)。

即最后的结果为

      x=r1t1M1+r2t2M2+···+antnMn+kM (K ⊆ Z )

至此中国剩余定理证毕。代码如下(逆元使用拓展欧几里得算法求得):

非互质的中国剩余定理

刚刚说到的中国剩余定理全部要求两两互质,这是为什么呢?

如果不互质的话,也会有一些式子有解,比如

x  ≡  13(mod  12)
x  ≡  5(mod 10)

这个方程组有一个解25。不过也有一些不互质的并没有解,那么,如何判断一个不互质的方程组有没有解,又如何把它们的解求出来呢?

mi非互质,对于前两个方程

xa1(mod m1)

xa2(mod m2)

x=a1+m1y1

x=a2+m2y2

m1y1m2y2=a2a1

这是一个可以用拓展欧几里得求解的式子,要想有解,必然有gcd(m1,m2)可以整除(a2-a1),如果不能,这个方程组就没有解,这里我们假设有解,用拓展欧几里得继续解出最小y1,并且可得x=a1+m1y1

即两个方程可以合成为yx(mod lcm(m1,m2))

一只合并下去,就可以得到最终结果。 

若方程无解,无法合并,则最终无解。

 

代码如下:

 

Lucas定理

接下来我们来看另一个相关算法,Lucas定理。

Lucas定理是用来求c(n,m) mod p (p为素数)的一种算法。老规矩,仍然先看结论:

Lucas(n,m,p)=c(n%p,m%p)*Lucas(n/p,m/p,p)  (其中n>m, p为模数)

体现到程序中,可以递归调用实现C(n,m)的计算。递归结束条件为m=0。该算法的最大数据处理范围大概在10左右。

下面我们对该定理进行证明。

我们通过二项式定理来证,首先令n=sp+q , m=tp+r,则Lucas定理的形式转化为C(sp+q,tp+r)=C(s,t)*C(q,r) (mod p)。将(1 + x) n化简展开:

(1 + x) n=(1 + x) sp+q =( (1 + x)p)s· (1 + x) q 

( (1 + x)p)s· (1 + x) q (1 + xp) s· (1 + x) q(mod p)

之前一直很困惑第二个式子怎么来的,明白之后发现很简单。注意到同余的可乘性和可加性,我们可以在这里把(1 + x)p进行二项式展开,除去第一项C(p,0)和最后一项C(p,p)xp,其他的项都满足C(p,i)的形式,而这个式子是可以被p整除的(p!/((p-i)!*i!)),因此全部可以消掉。

现在我们故技重施,再次将二项式展开,得到

(1 + xp) s· (1 + x)(mod p)

(1 + x) sp+q (mod p)

这时候,我们在左边的展开式中能够找到C(sp+q,tp+r)*xtp+r这一项,而在式子右边要想构造这一项,只能让i=t,j=r,才能凑出xtp+r

而此时,左边的二项式系数为C(sp+q,tp+r),右边的系数为C(s,t)*C(q,r),即

C(sp+q,tp+r) ≡C(s,t)*C(q,r) (mod p)

n=sp+q , m=tp+r代回,可得

C(n,m) ≡C(n/p,m/p)*C(n%p,m%p) (mod p)

至此,Lucas定理证毕。

利用Lucas定理可以很方便的计算大组合数取模问题,代码如下

非质数的Lucas定理

需要注意,卢卡斯定理要求mod m必须为质数,实际上也会出不是质数的问题,这时候我们就需要Lucas定理配合中国剩余定理来解决,具体方法为,先将m质因数分解为p1*p2*p3*…*pn(p为质数)的形式,再对每个因子分别进行Lucas定理的求解,最后将所有的结果并列在一起进行中国剩余定理的求解,即可得到结果。

Update

  1. 需要逆元去进行除法计算的原因是不能同时进行乘法和取模,乘法完成之后可能结果已经过大。这个技巧在Lucas定理求组合数的过程中也有应用。
  2. 逆元的最小解为求出的解 mod m。

发表评论

电子邮件地址不会被公开。 必填项已用*标注