题目:

求ax+by=c的一组解,使得abs(x)+abs(y)尽量小,满足前面前提下abs(ax)+abs(by)尽量小


题解:

exgcd之后,分别求出让x尽量小和y尽量小的解,取min即可

 #include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int a,b,c,x,y,u1,u2,v1,v2,g;
int exGcd(int a,int b,int &x,int &y)
{
if (b==) return x=,y=,a;
int r=exGcd(b,a%b,y,x);
y-=(a/b)*x;
return r;
}
int main()
{
while (scanf("%d%d%d",&a,&b,&c),a+b+c>)
{
g=exGcd(a,b,x,y);
a/=g,b/=g,c/=g;
u1=(x%b*c%b+b)%b;
v1=(c-u1*a)/b;
if (v1<) v1=-v1;
v2=(y%a*c%a+a)%a;
u2=(c-v2*b)/a;
if (u2<) u2=-u2;
if (u1+v1>u2+v2 || (u1+v1==u2+v2 && a*u1+b*v1>a*u2+b*u2))
u1=u2,v1=v2;
printf("%d %d\n",u1,v1);
}
return ;
}

最新文章

  1. win7安装oracle11g64位提示环境变量Path长度超出
  2. shutdown的简单小应用
  3. vc++用ADO方式连接oracle问题
  4. JQuery 定时器 (Jquery Timer 插件)
  5. jQ处理页面中尺寸过大的图片
  6. html 定位问题
  7. on delete cascade 和on update cascade
  8. ISP与IAP的区别
  9. 序列化对象C++对象的JSON序列化与反序列化探索
  10. android.util.AndroidRuntimeException: requestFeature() must be called before adding content 错误解决方法
  11. 2.5.5 使用DatePickerDialog, TimePickerDialog
  12. 零散的笔记:jquery中的事件
  13. unity 打包 windows 运行 紫色 粉红色
  14. SQL SERVER 的前世今生--各版本功能对比
  15. 浏览器控制台console的使用
  16. 2018-2019-2 20165337《网络攻防技术》Exp5 MSF基础应用
  17. go语言学习--内核态和用户态(协程)
  18. java锁
  19. ef core 相关
  20. 边缘触发(Edge Trigger)和条件触发(Level Trigger)

热门文章

  1. 连接MYSQL 错误代码2003
  2. Servlet学习笔记01——什么是servlet?
  3. shell脚本结构化语句
  4. [USACO1.5] 回文质数
  5. Gold Balanced Lineup POJ - 3274
  6. 笔记-python-module-logging.循环日志、多进程日志
  7. get请求中url传参中文乱码问题
  8. MySQL之查询性能优化(一)
  9. echarts 地图的背景色和各省颜色配置以及地图饼图联动
  10. erlang中的原子(atom)内部实现[转]