poj2142 The Balance 扩展欧几里德的应用稍微还是有点难度的

题目意思一开始没理解，原来是给你重为a,b,的砝码求测出重量为d的砝码，a,b砝码可以无限量使用

开始时我列出来三个方程 :

a*x+b*y=d;

a*x-b*y=d;

b*y-ax=d;

傻眼了，可是我们知道 x,y前面的正负符号是不影响extgcd的使用的，比如poj1061 方程式是 px+qy=m,而 nefu84方程式是：px-qy=m；

所以不影响只是方法没有想好，后来想到了先令ax+by=1,求解出 x,y再乘以d不就可以了吗？

一开始球ax+by=1时我居然直接使用了 extgcd ，然后解出x0,y0,则x=x0*1/gcd值，可是这道题目的 a,b的gcd不一定为1，所以1/gcd会等于0，所以这道题目一定要先求出a,b,的gcd值，然后 a/=gcd,b/=gcd,d/=gcd,这样再求出x,y,的值就不需要再乘以 1/gcd啦，好开心感觉越做自信越高了

接下里的话题目对于 x,y是有要求的要x+y尽量小，ax+by尽量小，你求出的 x,y中有可能的是有负的，那很正常，因为题目要求的是测出d的重量，所以有可能是

：

a*x+b*y=d;

a*x-b*y=d;

b*y-ax=d;

但是题目要求是正的这时候就是考验对扩展欧几里德了解程度了下面贴出关于这部分的性质：

对于不定整数方程pa+qb=c，若 c mod Gcd(a, b)=0,则该方程存在整数解，否则不存在整数解。

上面已经列出找一个
整数解的方法，在找到p * a+q * b = Gcd(a, b)的一组解p0,q0后，
/*p * a+q * b = Gcd(a, b)的其他整数解满足：

p = p0 + a/Gcd(a, b) * t

q = q0 - b/Gcd(a, b) * t(其中t为任意
整数)

至于pa+qb=c的整数解，只需将p * a+q * b = Gcd(a, b)的每个解乘上 c/Gcd(a, b) 即可

在找到p * a+q * b = Gcd(a, b)的一组解p0,q0后，应该是

得到p * a+q * b = c的一组解p1 = p0*(c/Gcd(a,b)),q1 = q0*(c/Gcd(a,b))，p * a+q * b = c的其他整数解满足：

p = p1 + b/Gcd(a, b) * t

q = q1 - a/Gcd(a, b) * t(其中t为任意
整数)

p 、q就是p * a+q * b = c的所有
整数解。

就是运用扩展欧几里德求出的 p，q给的是最小的那一组有可能是负的而题目明显要求了 x不能为负，所以要利用上述性质来求出最小正解

先求出最小正解的x1然后利用式子 y1=(d-a*x1)/b;

然后求出最小正解 y2，然后利用式子x2=(d-b*y2)/a;

然后比较 x1+y1 x2+y2的大小取小的那一组

#include<iostream>

#include<cstdio>

#include<list>

#include<algorithm>

#include<cstring>

#include<string>

#include<queue>

#include<stack>

#include<map>

#include<vector>

#include<cmath>

#include<memory.h>

#include<set>

#define ll long long

#define LL __int64

#define eps 1e-8

const ll INF=9999999999999;

#define M 400000100

#define inf 0xfffffff

using namespace std;

//vector<pair<int,int> > G;

//typedef pair<int,int> P;

//vector<pair<int,int>> ::iterator iter;

//

//map<ll,int>mp;

//map<ll,int>::iterator p;

//

//vector<int>G[30012];

ll GCD(ll a,ll b)

{

	while(b)

	{

		ll r=b;

		b=a%b;

		a=r;

	}

	return a;

}

ll extgcd(ll a,ll &x,ll b,ll &y)

{

	if(b==0)

	{

		x=1;

		y=0;

		return a;

	}

	ll r=extgcd(b,x,a%b,y);

	ll t=x;

	x=y;

	y=t-a/b*y;

	return r;

}

int main(void)

{

	ll a,b,d;

	while(cin>>a>>b>>d)

	{

		if(a+b+d == 0)

			break;

		ll x0,y0;

		ll gcd=GCD(a,b);//这里要先求出 a,b的gcd值

		a/=gcd;

		b/=gcd;

		d/=gcd;//都除以gcd

		extgcd(a,x0,b,y0);

		ll x=x0*d;

		ll y=y0*d;//求出的 x0就不需要 乘以1/gcd 了，

		ll x1=x,y1=y;

		x1=(x%b+b)%b;//这里是假设不知道x,y的正负情况，求出x1的最小正解

		y1=(d-x1*a)/b;//对应x1的y1最小正解

		if(y1<0)

			y1=0-y1;

		ll x2=x,y2=y;

		y2=(y2%a+a)%a;//这里是假设不知道x,y的正负情况，求出y2的最小正解

		x2=(d-y2*b)/a;//对应x2的y1最小正解

		if(x2<0)

			x2=0-x2;

		if(x1+y1 > x2+y2)//比较 x1+y1 x2+y2的大小

			x=x2,y=y2;

		else

			x=x1,y=y1;

		cout<<x<<" "<<y<<endl;

	}

}

巴特西

poj2142 The Balance 扩展欧几里德的应用稍微还是有点难度的

最新文章

热门文章

巴特西

poj2142 The Balance 扩展欧几里德的应用 稍微还是有点难度的

最新文章

热门文章

poj2142 The Balance 扩展欧几里德的应用稍微还是有点难度的