同余问题

同余即余数相同。同余问题是$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
2
3
4
int gcd(int a, int b) {
if (!b) return a;
else return gcd(b, a % b);
}

扩展欧几里得算法(exgcd)

扩展欧几里得算法可以用来求解不定方程$ax+by=\gcd(a,b)$,其中$a$和$b$是已知的。且$a,b,x,y\in Z$。

算法原理

代码实现

1
2
3
4
5
6
7
void exgcd(int a, int b, int &d, int &x, int &y) {
if (!b) d = a, x = 1, y = 0;
else {
exgcd(b, a % b, d, y, x);
y -= x * (a / b);
}
}

应用

可以用来解同余方程。对于$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$的值,方程组得以合并。