C++实现,拓展中国剩余定理——解同余方程组(理论证明和代码实现)
拓展中国剩余定理
前言
记得半年前还写过关于拓展中国剩余定理的博客。。。不过那时对其理解还不是比较深刻,写的也比较乱。
于是趁学校复习之机,再来重温一下拓展中国剩余定理(以下简称ExCRT)
记得半年前还写过关于拓展中国剩余定理的博客。。。不过那时对其理解还不是比较深刻,写的也比较乱。
于是趁学校复习之机,再来重温一下拓展中国剩余定理(以下简称ExCRT)
一些理论准备
拓展欧几里得解不定方程
对于不定方程\(a*x+b*y=gcd(a,b)\),视a,b为常数,我们有一种通用的方法来求一组特解:
LL exgcd(LL a,LL b,LL &x,LL &y) {
if(b==0) { x=1,y=0; return a; }
LL d=exgcd(b,a%b,y,x);
y-=(a/b)*x;
return d;
}
注:这种方法只能求一种特解,对于求所有的解请读者自行百度。这个函数运行到最后,x,y便是一组特解,返回值为\(gcd(a,b)\)。
于是我们可以将这个方程推广为解类似于\(a*x+b*y=c\)这个不定方程,方法就是先求出方程\(a*x'+b*y'=gcd(a,b)\)的解,之后将等式两边同时乘以\(c/gcd(a,b)\)。便转换为:
\(a*x'*c/gcd(a,b)+b*y'*c/gcd(a,b)=c\),\(x=x'*c/gcd(a,b),y=y'*c/gcd(a,b)\).
而如果c并不能被\(gcd(a,b)\)整除,那么此不定方程无解
理论证明
对于同余方程:
\(\left\{\begin{matrix}x\equiv r_{1}(mod\: m_{1}) & & \\ x\equiv r_{2}(mod\: m_{2}) & & \\ ...... & & \\x\equiv r_{k}(mod\: m_{k}) \end{matrix}\right.\)
我们可以考虑\(k=2\)的情况,也就是解如下方程:
\(\left\{\begin{matrix}
x\equiv r_{1}(mod\: m_{1})\\
x\equiv r_{2}(mod\: m_{2})
\end{matrix}\right.\)
由如上方程不难转换为以下形式
\(\left\{\begin{matrix}
x=k1*m1+r1\\
x=k2*m2+r2
\end{matrix}\right.\)
将两个式子合并可以得到:
\(k1*m1-k2*m2=r2-r1\)
对于这个不定方程,我们可以使用拓展欧几里得来求解。
先解出方程\(k1'*m1-k2'*m2=gcd(m1,m2)\),于是可以得到
\(k1=k1'*(r2-r1)/gcd(m1,m2)\),代入式子\(x=k1*m1+r1\)便可以算出x的一组特解,设这个特解为\(x0\),那么可以得到通解
\(x=x0+t*lcm(m1,m2)\),于是我们便通过合并第1,2个同余式子得到了新的一个同余方程:\(x\equiv x0(mod\: lcm(m1,m2))。\)
将这个同余方程按照同样的方法与第三个同余式子合并,最后只剩下唯一一个式子\(x\equiv x_{k}(mod\: lcm(所有模数m_{i}))\)。
此时的答案便可以得出最小的答案。
代码实现
LL ExCRT() {
LL M=m[1],R=r[1];
//方便 理解代码的话
//m可以看作上述x0,R可以看作lcm(m1,m2)
for(LL i=2,d,x,y;i<=n;i++) {
d=exgcd(M,m[i],x,y);//d为最大公约数
if((R-r[i])%d) return -1;//无解的情况
x=x*(R-r[i])/d%m[i];
R-=x*M;
M=M/d*m[i];
R%=M;
}
return (R%M+M)%M;//最小的正整数解
}
写在后面
现在发现。。。ExCRT好简单
最新文章
- Mysql常用函数,难点,注意
- Bash:-:-定义空变量作为输出结合换行符\n和column输出
- php : 匿名函数(闭包) [二]
- Extjs各版本的下载链接
- Redis高级实践之————Redis短连接性能优化
- matlab语言基础
- NFC Forum : Frequently Asked Questions (NFC 论坛:FAQ)
- elasticsearch中的mapping映射配置与查询典型案例
- UVA11538Chess Queen(组合数学推公式)
- 代码中实际运用memcached——.NET
- C++ Primer 学习笔记_57_类和数据抽象 --管理指针成员
- Oracle如何还原数据库
- linux重新设置密码,亲试成功
- margin塌陷
- leetcode python 009
- mac删除python
- Oracle VM VirtualBox如何设置网络地址转换NAT
- FormatSQL
- Linux iptables常用命令的使用
- webapi中取文件的物理路径(server.mappath)