同余即余数相同,同余问题是OI中比较经典的问题。
前言
之前的时候作者一直想要学习数论,可无奈……每一次都咕掉了没时间
而今天,作者终于抽出了一个晚上。
于是,便有了这篇博客。
基本概念&定义
在本文中,我们主要讲解同余问题。
在讲解之前,我们先来了解一点有关余数的基本概念。
整除
假设我们有两个整数 $a$ , $b$,若$ka = b$, 则我们称$b$整除$a$,记为$a|b$。
取模
模数即余数,在数学中,我们把整数$a$与整数$b$的模数记为$amod b$。
在这里,$mod$相当于C++中的$%$运算。
根据定义,我们可以得出$a mod b = a - ⌊frac{a}{b}⌋ times b$。
同余
若$a mod c = b mod c$, 则称$a$与$b$在模$c$意义下同余,写作$a equiv b (mod c)$
模运算的基本性质
下面给出几个模运算的基本性质,请各位读者自行证明。
其中,第一个公式就是上面取模部分的公式
$$a mod b = a - ⌊frac{a}{b}⌋ times b$$
$$a equiv b(mod m) iff m | (a − b)$$
$$b equiv c iff a + b equiv a + c$$
以上的公式均满足$a , b , c , m ∈ Z$
Gcd(欧几里得算法)
gcd
是最大公约数的英文缩写(也是某个红色政治组织的简称),$a$与$b$的最大公约数记为$gcd(a , b)$
而欧几里得算法专门用来求两个数的$gcd$,下面,我们就对其进行证明。
求证
$$gcd(a , b) = gcd(b , amod b)$$
证明
当$a < b$时,我们交换$a$与$b$的位置,这样我们只需要考虑$a > b$的情况.
当$a > b$时,有
$$a = kb + r (k , r ∈ Z)$$
其中,$r$为$a mod b$,$k$为$⌊frac{a}{b}⌋$。
现在我们移项,可得
$$r = a - kb $$
$$because gcd(a , b) | a , gcd(a , b) | b$$
$$therefore gcd(a , b) | a - k times b$$
$$therefore gcd(a , b) | r$$
$$because r = a mod b$$
$$therefore gcd(a , b) | a mod b$$
$$therefore gcd(a , b) = gcd(b , amod b)$$
大功告成啦ヾ(^∀^)ノ
Code
直接递归实现,边界条件为$b = 0$,若$b = 0$,直接返回$a$即可
int (int a , int b){ |
顺便求一下两个数的最小公倍数
$$lcm(a , b) = frac{atimes b}{gcd(a , b)}$$
int lcm(int a , int b){ |
Exgcd(扩展欧几里得)
exgcd
相当于$Gcd$的升级版,它可以在求出$gcd(a , b)$的同时求出二元一次不定方程 $ax + by = gcd(a , b)$的一组整数解。
其中,$a$,$b$均为已知的,且$a , b , x , y ∈ Z$。
举个栗砸
在求$gcd(71 , 13)$时,我们得到了以下式子
$$71 = 13 times 5 + 6$$
$$13 = 6 times 2 + 1$$
现在我们移一下项,把余数都移到左边,就成了下面这个样子
$$6 = 71 + 13times (-5)$$
$$1 = 13 + 6times (-2)$$
从$gcd(71 , 13)$开始,把我们刚刚推出的式子一一带入,就成了下面的样子
$gcd(71 , 13)$
$= 1$
$= 13 + 6times (-2)$
$= 13 + [71 + 13times(-5)]times(-2)$
$= 13 times 11 + 71 times (-2)$
$= 71 times (-2) + 13 times 11$
看最后一个式子,是不是就是$a = 71$ ,$b = 13$时的不定方程?
所以解为$x = -2$, $y = 11$。
Code
int exgcd(int a , int b , int g , int &x , int &y ){ |
参考资料
鸣谢上面两位dalao在数论学习方面给予我的帮助
近期评论