扩展欧几里得算法求二元一次方程
2023-02-18 16:34:33 时间
二元一次方程的定义:
含有两个未知数,并且含有未知数的项的次数都是1的整式方程做二元一次方程。所有二元一次方程都可化为ax+by+c=0(a、b≠0)的一般式与ax+by=c(a、b≠0)的标准式,否则不为二元一次方程。
求最大公约数
int gcd(int a,int b)//a,b为两个数。
{
if(b==0)
return a;
else
return gcd(b,a%b);
}
拓展欧几里得算法
int exgcd(int a,int b,int &x,int &y)
{
if(b==0){
x=1;
y=0;
return a;
}
else{
int r=exgcd(b,a%b,y,x);
y-=(a/b)*x;
return r;
}
}
求一组特解代码:
if(n%__gcd(a,b) == 0){ //第一步判断方程是否有整数解
exgcd(a,b,x,y);//第二步求方程 ax+by=gcd(a,b) 的一个特解
x = x*n/__gcd(a,b); //第三步计算 ax+by=n 的解
y = y*n/__gcd(a,b);
cout<<x<<" "<<y<<endl;
}
求通解
现在我们来考虑构造通解( 特解是X、Y ):
由于已经满足 , 两个未知数的关系类似于加权和固定,若一个增大,则另一个一定按比例减小,显然满足关系:
X 每变化 b 的整数倍,Y 就反向变化 a 的同等倍数。似乎构造出了通解表达式 、
。
但是我们会发现一个问题,就是 a 、b 不一定是最小的步长,可能会 “跳过” 许多解。
为了求得最小步长,我们应该对 a 、b 同时除以某个整数,使得商也是整数,就求出了每次最小的变化量。很明显,应除以
所以,通解应该是
举例:(待修改)
for(int i=0;i<=1000;i++){
int newx = x+i*b/__gcd(a,b);
int newy = y-i*a/__gcd(a,b);
if(newx>=0&&newy>=0){
cout<<"newx= "<<newx<<" newy="<<newy<<endl;
}
}
参考:
https://blog.csdn.net/weixin_43810158/article/details/87973511
https://blog.csdn.net/Originum/article/details/81437027
相关文章
- 首个在ImageNet上精度超过80%的二值神经网络BNext问世,-1与+1的五年辛路历程
- Redis+Guava,性能炸裂!这组合真的太顶了....
- 【eureka问题:已解决】Request execution failed with message: java.net.ConnectException: Connection refused:
- 【已解决】Cannot connect to the Docker daemon at unix:///var/run/docker.sock. Is the docker daemon runnin
- 【已解决】springboot在使用redisTemplate的测试的时候报空指针
- 差两个像素让我很难受,这问题绝不允许留到明年!
- React DevUI 18.0 正式发布🎉
- 好慌,我代码没了!不会是变基变出问题了吧?
- 老板:你为什么要选择 Vue?
- 实用的 Bash 快捷键
- Quill基本使用和配置 - DevUI
- Quill富文本编辑器的实践 - DevUI
- 如何解决异步接口请求快慢不均导致的数据错误问题? - DevUI
- 让我们一起建设 Vue DevUI 项目吧!🥳
- 号外号外!DevUI Admin V1.0 发布啦!
- 手把手教你搭建自己的Angular组件库 - DevUI
- 2021 年最值得推荐的 7 个 Angular 前端组件库 - DevUI
- 立完flag,你可能需要对flag进行量化
- html2canvas实现浏览器截图的原理(包含源码分析的通用方法)
- 在瀑布下用火焰烤饼:三步法助你快速定位网站性能问题(超详细)