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

前言

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

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

于是,便有了这篇博客。


基本概念 & 定义

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

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

整除

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

取模

模数即余数,在数学中,我们把整数 a 与整数 b 的模数记为 amodb

在这里,mod 相当于 C++ 中的 % 运算。

根据定义,我们可以得出 amodb=aab×b

同余

amodc=bmodc, 则称 a b 在模 c 意义下同余,写作 ab(modc)

模运算的基本性质

下面给出几个模运算的基本性质,请各位读者自行证明。

其中,第一个公式就是上面取模部分的公式

amodb=aab×bab(modm)m|(ab)bca+ba+c

以上的公式均满足 a,b,c,mZ


Gcd (欧几里得算法)

gcd 是最大公约数的英文缩写 (也是某个红色政治组织的简称)a b 的最大公约数记为 gcd(a,b)

而欧几里得算法专门用来求两个数的 gcd,下面,我们就对其进行证明。

求证

gcd(a,b)=gcd(b,amodb)

证明

a<b 时,我们交换 a b 的位置,这样我们只需要考虑 a>b 的情况.

a>b 时,有

a=kb+r(k,rZ)

其中,r amodbkab

现在我们移项,可得

r=akbgcd(a,b)|a,gcd(a,b)|bgcd(a,b)|ak×bgcd(a,b)|rr=amodbgcd(a,b)|amodbgcd(a,b)=gcd(b,amodb)

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

Code

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

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

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

lcm(a,b)=a×bgcd(a,b)
cpp
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,yZ

举个栗砸

在求 gcd(71,13) 时,我们得到了以下式子

71=13×5+613=6×2+1

现在我们移一下项,把余数都移到左边,就成了下面这个样子

6=71+13×(5)1=13+6×(2)

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

gcd(71,13)
=1
=13+6×(2)
=13+[71+13×(5)]×(2)
=13×11+71×(2)
=71×(2)+13×11

看最后一个式子,是不是就是 a=71 ,b=13 时的不定方程?

所以解为 x=2, y=11

Code

cpp
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