d.用2种砝码,质量分别为a和b,称出质量为d的物品。求所用的砝码总数量最小(x+y最小),并且总质量最小(ax+by最小)。

s.扩展欧几里得求解不定方程。

设ax+by=d.

题意说不定方程一定有解。对于不定整数方程pa+qb=c,若 c mod Gcd(p, q)=0,则该方程存在整数解,否则不存在整数解。

也就是说,d mod gcd(a,b)=0.

a,b,d同时除以gcd(a,b)得到a'x+b'y=d';

用扩展欧几里德求出 a'x+b'y=gcd(a',b')=1的解(x,y),

那么原来这个a'x+b'y=d'的解就是(x*d',y*d')。

然后分两种情况来求就行了(假设物品放右边):

(1)令x是最小正整数,a放左边的最优解;(y<0代表b放右边)

(2)令y是最小正整数,b放左边的最优解;

两者中x+y小的就是结果。

c.

#include<iostream>
#include<stdio.h>
using namespace std; int gcd(int a,int b){
return b?gcd(b,a%b):a;
} int ex_gcd(int a,int b,int &x,int &y){
if(b==){
x=;
y=;
return a;
}
int d=ex_gcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
return d;
} int main(){ int a,b,d; int q;//a,b的最大公约数
int x,y;
int x1,y1;
int x2,y2; while(~scanf("%d%d%d",&a,&b,&d)){
if(a==&&b==&&d==)break; q=gcd(a,b);
//这里 对于不定整数方程pa+qb=c,若 c mod Gcd(p, q)=0,则该方程存在整数解,否则不存在整数解。
//不定方程:ax+by=d
a=a/q;
b=b/q;
d=d/q;//题目一定有解,可以整除 //不定方程:ax+by=d q=ex_gcd(a,b,x,y);//求的是ax+by=gcd(a,b)=1 //令x是最小正整数,a放左边的最优解
x1=x*d;
x1=(x1%b+b)%b;//x变为最小正整数
y1=(d-a*x1)/b;
if(y1<){
y1=-y1;
} //令y是最小正整数,b放左边的最优解
y2=y*d;
y2=(y2%a+a)%a;//y变为最小正整数
x2=(d-b*y2)/a;
if(x2<){
x2=-x2;
} //x+y和最小
if(x1+y1<x2+y2){
printf("%d %d\n",x1,y1);
}
else{
printf("%d %d\n",x2,y2);
} } return ;
}

最新文章

  1. javascript 常见方法记录
  2. FileOutputStream和FileInputStream的用法
  3. 编写更少量的代码:使用apache commons工具类库
  4. ups机制下停电提前关闭oracle数据库
  5. 如何查看 oracle 官方文档
  6. mongo(三)基本操作
  7. c++ template函数的声明和实现需要在同一个文件中
  8. mvvm架构使用解析
  9. javascript 和 jquery 语法上的一些区别
  10. z
  11. Github Blog 搭建手册
  12. Linux下passwd和shadow文件内容详解
  13. 58 同城 iOS 客户端 iOS11 及 iPhone X 适配实践
  14. 详解最大似然估计(MLE)、最大后验概率估计(MAP),以及贝叶斯公式的理解
  15. 使用sessionStorage、localStorage存储数组与对象
  16. connected standby
  17. 【M2】软件工程终期总结报告——前端设计总结
  18. Angular基础(五) 内建指令和表单
  19. python构建bp神经网络_曲线拟合(一个隐藏层)__1.可视化数据
  20. web.py利用模板的详细步骤

热门文章

  1. Python入门--13--爬虫一
  2. linux的cpu性能评估
  3. elasticsearch入门使用(三) Query DSL
  4. R 包安装、载入和卸载
  5. Codeforces 514C Watto and Mechanism(字典树)
  6. CodeForces - 813C The Tag Game (树的dfs遍历)
  7. linux下查看隐藏文件
  8. activiti实现的请假流程
  9. linux命令stat,查看文件详细信息
  10. gdb源码安装,指定使用的python版本