【数学】同余问题

同余即余数相同，同余问题是OI中比较经典的问题。

前言

之前的时候作者一直想要学习数论，可无奈……每一次都咕掉了没时间

而今天，作者终于抽出了一个晚上。

于是，便有了这篇博客。

---

基本概念&定义

在本文中，我们主要讲解同余问题。

在讲解之前，我们先来了解一点有关余数的基本概念。

整除

假设我们有两个整数 $a$ , $b$，若$ka = b$， 则我们称$b$整除$a$，记为$a|b$。

取模

模数即余数，在数学中，我们把整数$a$与整数$b$的模数记为$a\mod 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 , a\mod 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 , a\mod b)$$

大功告成啦ヾ(^∀^)ﾉ

Code

直接递归实现，边界条件为$b = 0$，若$b = 0$，直接返回$a$即可

int gcd(int a , int b){
    return !b ? a : gcd(b , a % b);
}

顺便求一下两个数的最小公倍数

$$lcm(a , b) = \frac{a\times b}{gcd(a , b)}$$

int lcm(int a , int b){
    return a / gcd(a , b) * 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 + 13\times (-5)$$ $$1 = 13 + 6\times (-2)$$

从$gcd(71 , 13)$开始，把我们刚刚推出的式子一一带入，就成了下面的样子

$gcd(71 , 13)$
$= 1$
$= 13 + 6\times (-2)$
$= 13 + [71 + 13\times(-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 ){
    if(b == 0){
        x = 1;
        y = 0;
        g = a;
    }
    else{
        exgcd(b , a % b , g , y , x);
        y -= x * (a / b);
    }
}

---

参考资料

1. Menci’s Blog

2. Struct 瓶子’s Blog

鸣谢上面两位dalao在数论学习方面给予我的帮助

---

THE END