同余即余数相同。同余问题是$OI$中比较常见的问题。
基本概念
整除
假设有两个整数$a$和$b$,且满足$ka = b (k \in Z)$,则称$b$整除$a$,记为$a | b$。
取模
模数也就是余数。整数$a$除以整数$b$的余数记为$a \bmod b$。
另一种形式的定义是:若$a=kb+r(a\ge b, a,k,b,r\in Z)$,则$a \bmod b=r$。
根据定义,我们可以得出$a\bmod b=a-\left\lfloor\frac{a}{b}\right\rfloor\times b$。
同余
若$a\bmod m = b\bmod m$,则$a$与$b$在模$m$意义下同余,记为$a \equiv b \pmod m$。
模运算
以下列出几个关于模运算的性质:
以上公式均满足$a,b,m\in Z$。
欧几里得算法(gcd)
用来求最大公约数。$a$和$b$的最大公约数记为$gcd(a,b)$。
算法原理
求证
$\gcd(a,b)=\gcd(b,a\bmod b)$
证明
当$a\le b$时,我们直接把$a$和$b$的值交换,将其转为$a\ge b$的情况。
当$a\ge b$时,有
移项得
边界处理
代码通常使用递归实现,递归边界为$b=0$,这时直接返回$a$的值即可。
代码实现
1 | int gcd(int a, int b) { |
扩展欧几里得算法(exgcd)
扩展欧几里得算法可以用来求解不定方程$ax+by=\gcd(a,b)$,其中$a$和$b$是已知的。且$a,b,x,y\in Z$。
算法原理
代码实现
1 | void exgcd(int a, int b, int &d, int &x, int &y) { |
应用
可以用来解同余方程。对于$ax\equiv b\pmod m$,它等价于$ax+my=b$,这个不定方程正好和扩展欧几里得算法求解的不定方程形式相同,因此我们考虑用此算法求解。
用$exgcd$求出方程$ax+my=\gcd(a,m)$的解,然后我们考虑如何将其转为方程$ax+my=b$。根据我们之前讲到的一个性质,我们在方程左右同时乘$\frac{b}{\gcd(a,m)}$,方程仍然成立,而右边的$\gcd(a,m)$则变为了$b$,于是我们轻而易举得到了方程$\frac{axb}{\gcd(a,m)}+\frac{myb}{\gcd(a,m)}=b$的整数解。这里的$\frac{axb}{\gcd(a,m)}$和$\frac{myb}{\gcd(a,m)}$就是我们要求的其中一组解。
需要注意的是,如果$\gcd(a,m) | b$不成立,则没有上述求解过程,该方程无整数解。反之则有无数组整数解。
现在我们仅仅是求出了任意的一组解,并不能满足题目的某些要求,比如要求出该方程的最小正整数解,我们直接输出算法求出的解很可能不能满足要求。假设我们已经求出了方程$ax+my=b$的一组解,要在调整解的同时保持方程成立,我们可以用$\frac{m}{\gcd(a,m)}$来调整$x$的值,用$\frac{a}{\gcd(a,m)}$来调整$y$的值。
扩展中国剩余定理(excrt)
可以用来解同余方程组。算法过程简单说就是把若干个同余方程合并为一个,最后就可以方便地求解。
算法原理
考虑合并这个方程组$\begin{cases}x\equiv a_1\pmod{m_1}\\x\equiv a_2\pmod{m_2}\end{cases}$为$x\equiv a\pmod{m}$
设$m=lcm(m_1,m_2)$
则显然$a=a_1+um_1=a_2+vm_2$
移项得$um_1-vm_2=a_1-a_2$
exgcd可求解$u$,$v$
然后就可以求出$a$的值,方程组得以合并。