POJ - 2142 The Balance(扩展欧几里得求解不定方程)
2024-09-08 00:38:00
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 ;
}
最新文章
- javascript 常见方法记录
- FileOutputStream和FileInputStream的用法
- 编写更少量的代码:使用apache commons工具类库
- ups机制下停电提前关闭oracle数据库
- 如何查看 oracle 官方文档
- mongo(三)基本操作
- c++ template函数的声明和实现需要在同一个文件中
- mvvm架构使用解析
- javascript 和 jquery 语法上的一些区别
- z
- Github Blog 搭建手册
- Linux下passwd和shadow文件内容详解
- 58 同城 iOS 客户端 iOS11 及 iPhone X 适配实践
- 详解最大似然估计(MLE)、最大后验概率估计(MAP),以及贝叶斯公式的理解
- 使用sessionStorage、localStorage存储数组与对象
- connected standby
- 【M2】软件工程终期总结报告——前端设计总结
- Angular基础(五) 内建指令和表单
- python构建bp神经网络_曲线拟合(一个隐藏层)__1.可视化数据
- web.py利用模板的详细步骤