同余
定义
设整数 \(m\ne0\)。若 \(m\mid(a-b)\),称 \(m\) 为模数(模),\(a\) 同余于 \(b\) 模 \(m\),\(b\) 是 \(a\) 对模 \(m\) 的剩余。记作 \(a\equiv b\pmod m\)。
否则,\(a\) 不同余于 \(b\) 模 \(m\),\(b\) 不是 \(a\) 对模 \(m\) 的剩余。记作 \(a\not\equiv b\pmod m\)。
这样的等式,称为模 \(m\) 的同余式,简称同余式。
根据整除的性质,上述同余式也等价于 \(a\equiv b\pmod{(-m)}\)。
如果没有特别说明,模数总是正整数。
式中的 \(b\) 是 \(a\) 对模 \(m\) 的剩余,这个概念与余数完全一致。通过限定 \(b\) 的范围,相应的有 \(a\) 对模 \(m\) 的最小非负剩余、绝对最小剩余、最小正剩余。
性质
- 自反性:\(a\equiv a\pmod m\)。
- 对称性:若 \(a\equiv b\pmod m\),则 \(b\equiv a\pmod m\)。
- 传递性:若 \(a\equiv b\pmod m,b\equiv c\pmod m\),则 \(a\equiv c\pmod m\)。
- 线性运算:若 \(a,b,c,d\in\mathbf{Z},m\in\mathbf{N}^*,a\equiv b\pmod m,c\equiv d\pmod m\) 则有:
- \(a\pm c\equiv b\pm d\pmod m\)。
- \(a\times c\equiv b\times d\pmod m\)。
- 若 \(a,b\in\mathbf{Z},k,m\in\mathbf{N}^*,a\equiv b\pmod m\), 则 \(ak\equiv bk\pmod{mk}\)。
- 若 \(a,b\in\mathbf{Z},d,m\in\mathbf{N}^*,d\mid a,d\mid b,d\mid m\),则当 \(a\equiv b\pmod m\) 成立时,有 \(\dfrac{a}{d}\equiv\dfrac{b}{d}\left(\bmod\;{\dfrac{m}{d}}\right)\)。
- 若 \(a,b\in\mathbf{Z},d,m\in\mathbf{N}^*,d\mid m\),则当 \(a\equiv b\pmod m\) 成立时,有 \(a\equiv b\pmod d\)。
- 若 \(a,b\in\mathbf{Z},d,m\in\mathbf{N}^*\),则当 \(a\equiv b\pmod m\) 成立时,有 \(\gcd(a,m)=\gcd(b,m)\)。若 \(d\) 能整除 \(m\) 及 \(a,b\) 中的一个,则 \(d\) 必定能整除 \(a,b\) 中的另一个。
应用
扩展欧几里得算法
扩展欧几里得算法(Extended Euclidean algorithm, EXGCD),常用于求 \(ax+by=\gcd(a,b)\) 的一组可行解。
过程
设 \(ax_1+by_1=\gcd(a,b)\),\(bx_2+(a\bmod b)y_2=\gcd(b,a\bmod b)\)。
由欧几里得定理可知:\(\gcd(a,b)=\gcd(b,a\bmod b)\)。
所以 \(ax_1+by_1=bx_2+(a\bmod b)y_2\)。
又因为 \(a\bmod b=a-(\lfloor\frac{a}{b}\rfloor\times b)\)。
所以 \(ax_1+by_1=bx_2+(a-(\lfloor\frac{a}{b}\rfloor\times b))y_2\),
\(ax_1+by_1=ay_2+bx_2-\lfloor\frac{a}{b}\rfloor\times by_2=ay_2+b(x_2-\lfloor\frac{a}{b}\rfloor y_2)\)。
因为 \(a=a,b=b\),所以 \(x_1=y_2,y_1=x_2-\lfloor\frac{a}{b}\rfloor y_2\)。
将 \(x_2,y_2\) 不断代入递归求解直至 \(\gcd\)(最大公约数,下同)为 0
递归 x = 1, y = 0
回去求解。
实现
int exgcd(int a, int b, int &x, int &y){
if(b == 0){x = 1;y = 0;return a;}
else{
int d = exgcd(b, a % b, y, x);
y -= a / b * x;return d;
}
}
函数返回的值为 \(\gcd\),在这个过程中计算 \(x,y\) 即可。
值域分析
\(ax+by=\gcd(a,b)\) 的解有无数个,显然其中有的解会爆 long long
。
万幸的是,若 \(b\not= 0\),扩展欧几里得算法求出的可行解必有 \(|x|\le b,|y|\le a\),下面给出这一性质的证明。
证明:
\(\gcd(a,b)=b\) 时,\(a\bmod b=0\),必在下一层终止递归。
得到 \(x_1=0,y_1=1\),显然 \(a,b\ge 1\ge |x_1|,|y_1|\)。
\(\gcd(a,b)\not= b\) 时,设 \(|x_2|\le (a\bmod b),|y_2|\le b\)。
因为 \(x_1=y_2,y_1=x_2-{\left\lfloor\dfrac{a}{b}\right\rfloor}y_2\) 。
所以 \(|x_1|=|y_2|\le b,|y_1|\le|x_2|+|{\left\lfloor\dfrac{a}{b}\right\rfloor}y_2|\le (a\bmod b)+{\left\lfloor\dfrac{a}{b}\right\rfloor}|y_2|\)。
\(\le a-{\left\lfloor\dfrac{a}{b}\right\rfloor}b+{\left\lfloor\dfrac{a}{b}\right\rfloor}|y_2|\le a-{\left\lfloor\dfrac{a}{b}\right\rfloor}(b-|y_2|)\) 。
\(a\bmod b=a-{\left\lfloor\dfrac{a}{b}\right\rfloor}b\le a-{\left\lfloor\dfrac{a}{b}\right\rfloor}(b-|y_2|)\le a\)。
因此 \(|x_1|\le b,|y_1|\le a\) 成立。证毕。
中国剩余定理
引入
「物不知数」问题:有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?
即求满足以下条件的整数:除以 \(3\) 余 \(2\),除以 \(5\) 余 \(3\),除以 \(7\) 余 \(2\)。
该问题最早见于《孙子算经》中,并有该问题的具体解法。宋朝数学家秦九韶于 1247 年《数书九章》卷一、二《大衍类》对「物不知数」问题做出了完整系统的解答。上面具体问题的解答口诀由明朝数学家程大位在《算法统宗》中给出:
三人同行七十希,五树梅花廿一支,七子团圆正半月,除百零五便得知。
\(2\times 70+3\times 21+2\times 15=233=2\times 105+23\),故答案为 \(23\)。
定义
中国剩余定理 (Chinese Remainder Theorem, CRT) 可求解如下形式的一元线性同余方程组(其中 \(n_1, n_2, \cdots, n_k\) 两两互质):
\[\begin{cases} x &\equiv a_1 \pmod {n_1} \\ x &\equiv a_2 \pmod {n_2} \\ &\vdots \\ x &\equiv a_k \pmod {n_k} \\ \end{cases} \]上面的「物不知数」问题就是一元线性同余方程组的一个实例。
过程
- 计算所有模数的积 \(n\);
- 对于第 \(i\) 个方程:
- 计算 \(m_i=\frac{n}{n_i}\);
- 计算 \(m_i\) 在模 \(n_i\) 意义下的逆元 \(m_i^{-1}\);
- 计算 \(c_i=m_im_i^{-1}\)(不要对 \(n_i\) 取模)。
- 方程组在模 \(n\) 意义下的唯一解为:\(x=\sum_{i=1}^k a_ic_i \pmod n\)。
实现
题目描述
自从曹冲搞定了大象以后,曹操就开始捉摸让儿子干些事业,于是派他到中原养猪场养猪,可是曹冲满不高兴,于是在工作中马马虎虎,有一次曹操想知道母猪的数量,于是曹冲想狠狠耍曹操一把。举个例子,假如有 \(16\) 头母猪,如果建了 \(3\) 个猪圈,剩下 \(1\) 头猪就没有地方安家了。如果建造了 \(5\) 个猪圈,但是仍然有 \(1\) 头猪没有地方去,然后如果建造了 \(7\) 个猪圈,还有 \(2\) 头没有地方去。你作为曹总的私人秘书理所当然要将准确的猪数报给曹总,你该怎么办?
输入格式
第一行包含一个整数 \(n\) —— 建立猪圈的次数,接下来 \(n\) 行,每行两个整数 \(a_i, b_i\),表示建立了 \(a_i\) 个猪圈,有 \(b_i\) 头猪没有去处。你可以假定 \(a_1 \sim a_n\) 互质。
输出格式
输出包含一个正整数,即为曹冲至少养母猪的数目。
#include <iostream>
#define int long long
using namespace std;
int n, a[15], b[15];
int p = 1, t = 0;
int exgcd(int a, int b, int &x, int &y){
if(b == 0){x = 1;y = 0;return a;}
else{
int d = exgcd(b, a % b, y, x);
y -= a / b * x;return d;
}
}
int inv(int a, int p){
int x, y;exgcd(a, p, x, y);
return (x % p + p) % p;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n;
for(int i = 1 ; i <= n ; i ++)
cin >> a[i] >> b[i];
for(int i = 1 ; i <= n ; i ++)p *= a[i];
for(int i = 1 ; i <= n ; i ++)
t += (b[i] * p / a[i] * inv(p / a[i], a[i])) % p;
cout << t % p << endl;return 0;
}
证明
我们需要证明上面算法计算所得的 \(x\) 对于任意 \(i=1,2,\cdots,k\) 满足 \(x\equiv a_i \pmod {n_i}\)。
当 \(i\neq j\) 时,有 \(m_j \equiv 0 \pmod {n_i}\),故 \(c_j \equiv m_j \equiv 0 \pmod {n_i}\)。又有 \(c_i \equiv m_i \cdot (m_i^{-1} \bmod {n_i}) \equiv 1 \pmod {n_i}\),所以我们有:
\[\begin{aligned} x&\equiv \sum_{j=1}^k a_jc_j &\pmod {n_i} \\ &\equiv a_ic_i &\pmod {n_i} \\ &\equiv a_i \cdot m_i \cdot (m^{-1}_i \bmod n_i) &\pmod {n_i} \\ &\equiv a_i &\pmod {n_i} \end{aligned} \]即对于任意 \(i=1,2,\cdots,k\),上面算法得到的 \(x\) 总是满足 \(x\equiv a_i \pmod{n_i}\),即证明了解同余方程组的算法的正确性。
因为我们没有对输入的 \(a_i\) 作特殊限制,所以任何一组输入 \(\{a_i\}\) 都对应一个解 \(x\)。
另外,若 \(x\neq y\),则总存在 \(i\) 使得 \(x\) 和 \(y\) 在模 \(n_i\) 下不同余。
故系数列表 \(\{a_i\}\) 与解 \(x\) 之间是一一映射关系,方程组总是有唯一解。
证毕。
解释
下面演示 CRT 如何解「物不知数」问题。
- \(n=3\times 5\times 7=105\);
- 三人同行 七十 希:\(n_1=3, m_1=n/n_1=35, m_1^{-1}\equiv 2\pmod 3\),故 \(c_1=35\times 2=70\);
- 五树梅花 廿一 支:\(n_2=5, m_2=n/n_2=21, m_2^{-1}\equiv 1\pmod 5\),故 \(c_2=21\times 1=21\);
- 七子团圆正 半月:\(n_3=7, m_3=n/n_3=15, m_3^{-1}\equiv 1\pmod 7\),故 \(c_3=15\times 1=15\);
- 所以方程组的唯一解为 \(x\equiv 2\times 70+3\times 21+2\times 15\equiv 233\equiv 23 \pmod {105}\)。(除 百零五 便得知)
应用
某些计数问题或数论问题出于加长代码、增加难度、或者是一些其他原因,给出的模数:不是质数!
但是对其质因数分解会发现它没有平方因子,也就是该模数是由一些不重复的质数相乘得到。
那么我们可以分别对这些模数进行计算,最后用 CRT 合并答案。
扩展中国剩余定理:模数不互质的情况
两个方程
设两个方程分别是 \(x\equiv a_1 \pmod {m_1}\)、\(x\equiv a_2 \pmod {m_2}\);
将它们转化为不定方程:\(x=m_1p+a_1=m_2q+a_2\),其中 \(p, q\) 是整数,则有 \(m_1p-m_2q=a_2-a_1\)。
由裴蜀定理可知,当 \(a_2-a_1\) 不能被 \(\gcd(m_1,m_2)\) 整除时,无解;
其他情况下,可以通过扩展欧几里得算法解出来一组可行解 \((p, q)\);
则原来的两方程组成的模方程组的解为 \(x\equiv b\pmod M\),其中 \(b=m_1p+a_1\),\(M=\text{lcm}(m_1, m_2)\)。
多个方程
用上面的方法两两合并即可。
题目描述
给定 \(n\) 组非负整数 \(a_i, b_i\) ,求解关于 \(x\) 的方程组的最小非负整数解。
\[\begin{cases} x \equiv b_1\ ({\rm mod}\ a_1) \\ x\equiv b_2\ ({\rm mod}\ a_2) \\ ... \\ x \equiv b_n\ ({\rm mod}\ a_n)\end{cases} \]输入格式
输入第一行包含整数 \(n\)。
接下来 \(n\) 行,每行两个非负整数 \(a_i, b_i\)。
输出格式
输出一行,为满足条件的最小非负整数 \(x\)。
#include <iostream>
#define int __int128
#define MAXN 100005
using namespace std;
int x, y, d, n;
int a, b, A, B;
int read(){
int t = 1, x = 0;char ch = getchar();
while(!isdigit(ch)){if(ch == '-')t = -1;ch = getchar();}
while(isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * t;
}
void write(int x){
if(x < 0){putchar('-');x = -x;}
if(x >= 10)write(x / 10);
putchar(x % 10 ^ 48);
}
void exgcd(int a, int b, int &x, int &y){
if(b == 0){d = a;x = 1;y = 0;
}else{
exgcd(b, a % b, y, x);
y -= a / b * x;
}
}
int gcd(int a, int b){return b ? gcd(b, a % b) : a;}
int lcm(int a, int b){return a / gcd(a, b) * b;}
void merge(){
exgcd(a, A, x, y);int c = B - b;
if(c % d){puts("-1");exit(0);}
x = x * c / d % (A / d);
if(x < 0)x += A / d;
int mod = lcm(a, A);
b = (a * x + b) % mod;
if(b < 0)b += mod;
a = mod;
}
signed main(){
n = read();
for(int i = 1 ; i <= n ; i ++){
int _A, _B;
_A = read();_B = read();
A = _A;B = _B;
if(i > 1)merge();
else{a = A;b = B;}
}
write(b % a);putchar('\n');return 0;
}
标签:le,gcd,int,笔记,times,学习,pmod,同余,equiv
From: https://www.cnblogs.com/tsqtsqtsq/p/17795551.html