同余即余数相同,同余问题是 OI 中比较经典的问题。
前言
之前的时候作者一直想要学习数论,可无奈…… 每一次都咕掉了没时间
而今天,作者终于抽出了一个晚上。
于是,便有了这篇博客。
基本概念 & 定义
在本文中,我们主要讲解同余问题。
在讲解之前,我们先来了解一点有关余数的基本概念。
整除
假设我们有两个整数
取模
模数即余数,在数学中,我们把整数
在这里,
根据定义,我们可以得出
同余
若
模运算的基本性质
下面给出几个模运算的基本性质,请各位读者自行证明。
其中,第一个公式就是上面取模部分的公式
以上的公式均满足
Gcd (欧几里得算法)
gcd
是最大公约数的英文缩写 (也是某个红色政治组织的简称),
而欧几里得算法专门用来求两个数的
求证
证明
当
当
其中,
现在我们移项,可得
大功告成啦ヾ (^∀^)ノ
Code
直接递归实现,边界条件为
cpp
int gcd(int a , int b){ |
顺便求一下两个数的最小公倍数
cpp
int lcm(int a , int b){ |
Exgcd (扩展欧几里得)
exgcd
相当于
其中,
举个栗砸
在求
现在我们移一下项,把余数都移到左边,就成了下面这个样子
从
看最后一个式子,是不是就是
所以解为
Code
cpp
int exgcd(int a , int b , int g , int &x , int &y ){ |
参考资料
鸣谢上面两位 dalao 在数论学习方面给予我的帮助