poj 2142 扩展欧几里得解ax+by=c
2024-10-14 14:25:40
原题实际上就是求方程a*x+b*y=d的一个特解,要求这个特解满足|x|+|y|最小
套模式+一点YY就行了
总结一下这类问题的解法:
对于方程ax+by=c
设tm=gcd(a,b)
先用扩展欧几里得求出方程ax+by=tm的解x0、y0
然后有a*x0+b*y0=tm
令x1=x0*(c/tm),y1=y0*(c/tm)
则a*x1+b*y1=c
x1、y1即原方程的一个特解
这个方程的通解:xi=x1+k*(b/m),yi=y1-k*(a/m)
另:如果要求yi的最小非负解?令r=a/tm,则解y2=(y1%r+r)%r
针对本题,求出x1、y1后可以YY一下:
(1):若x1>0,y1>0,
1.y1-=(a/m),直到y1<0
2.y1+=(a/m),直到x1<0
(2):若x1<0,y1>0
y1-=(a/m),直到y1<0
易知最优解一定出现在这一咕噜里头,操作的同时更新最优答案即可。
#include <iostream>
#include <cmath>
using namespace std; int gcd(int a,int b){
if (b==) return a;
return gcd(b,a%b);
} int extgcd(int a,int b,int& x,int& y){
int d=a;
if (b!=){
d=extgcd(b,a%b,y,x);
y-=(a/b)*x;
}else{
x=;y=;
}
return d;
} int main()
{
int a,b,d,ax,ay,ans;
while (cin>>a>>b>>d)
{
if (a== && b== && d==) break;
else
{
int x,y;
int tm=extgcd(a,b,x,y);
int x1=x*(d/tm),y1=y*(d/tm);
int ra=a/tm,rb=b/tm;
y1=(y1%ra+ra)%ra;
x1=(d-y1*b)/a;
int x2=x1,y2=y1;
ans=abs(x2)+abs(y2);
ax=x2; ay=y2;
if (x2<)
{
while (y2>)
{
y2-=ra; x2+=rb;
if ((abs(y2)+abs(x2))<ans)
{
ans=abs(y2)+abs(x2);
ax=x2; ay=y2;
}
}
}
else if (x2>)
{
while (y2>)
{
y2-=ra; x2+=rb;
if ((abs(y2)+abs(x2))<ans)
{
ans=abs(y2)+abs(x2);
ax=x2; ay=y2;
}
}
x2=x1; y2=y1;
while (x2>)
{
y2+=ra; x2-=rb;
if ((abs(y2)+abs(x2))<ans)
{
ans=abs(y2)+abs(x2);
ax=x2; ay=y2;
}
}
}
cout<<abs(ax)<<" "<<abs(ay)<<endl;
}
}
return ;
}
最新文章
- dotnetcore 单元测试
- spring编程式刷新/重新加载applicationcontext/dispatchservlet(正确版)
- 夺命雷公狗—angularjs—18—angularjs的事件
- JavaScript(1)
- Java基础知识强化08:将字符串倒序输出(包括空格)的几种方法
- Linux 使用yum install安装mysql登陆不上解决办法
- uvalive3026 Period (KMP+结论)
- Hive的安装配置
- CentOS6.5 搭建基础PHP环境(yum安装)
- CSS3高级
- python sorted排序用法详解
- java基础--static关键字的使用
- HTML5轻松实现拍照上传功能[转载]
- MySQL5.6中date和string的转换和比较
- c语言第四次作业e
- (后端)mybatis中使用Java8的日期LocalDate、LocalDateTime
- Nginx、haproxy反向代理设置
- Jackson序列化LocalDate与Springboot集成
- adobe flash player不是最新版本
- spark restful 作业提交
热门文章
- Unity-WIKI 之 AnimationToPNG
- SQL Server进制
- Android优化—— Google 发布 Android 性能优化典范
- Android优化——UI优化(二) 使用include标签复用布局
- 程序4-6 utime函数实例
- 不支持一个 STA 线程上针对多个句柄的 WaitAll
- [py]导入模块3种方法
- [py]os.walk爬目录&sys.argv灵活获取参数
- Oracle的if else if
- 测试驱动开发实践 - Test-Driven Development(转)