【扩展欧几里得】POJ 2142 The Balance_C/C++_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > C/C++ > 【扩展欧几里得】POJ 2142 The Balance

【扩展欧几里得】POJ 2142 The Balance

 2011/11/8 7:50:27  基德KID.1412  http://972169909-qq-com.iteye.com  我要评论(1)
  • 摘要:http://poj.org/problem?id=2142不懂扩展欧几里得请先参照这里:http://972169909-qq-com.iteye.com/blog/1140914题意:输入3个数,前2个是砝码的种类,问各要多少个才能称出第三个数出来【同时要使2个答案之和最小】#include<iostream>#include<cmath>usingnamespacestd;#defineinf0x3fffffff#defineLL__int64LLgcd(LLa
  • 标签:
http://poj.org/problem?id=2142

不懂扩展欧几里得请先参照这里:
http://972169909-qq-com.iteye.com/blog/1140914

题意:输入3个数,前2个是砝码的种类,问各要多少个才能称出第三个数出来【同时要使2个答案之和最小】


#include <iostream>
#include <cmath>
using namespace std;
#define inf 0x3fffffff
#define LL __int64

LL gcd (LL a, LL b)
{
	return b ? gcd (b, a%b) : a;
}

LL Egcd (LL a, LL b, LL &x, LL &y)
{
	if (b == 0)
	{
		x = 1;
		y = 0;
		return a;
	}
	LL d = Egcd (b, a%b, x, y);
	LL tp = x;
	x = y;
	y = tp - a/b*y;
	return d;
}

int main()
{
	LL a, b, n, x, y, vx, vy, d;
	while (scanf ("%I64d%I64d%I64d", &a, &b, &n), (a||b||n))
	{
		d = gcd (a, b);
		a /= d;
		b /= d;
		n /= d;
		Egcd (a, b, x, y);
		/**********①令y是最小正整数解**********/
		vy = y*n;
		vy = (vy % a + a) % a;	//不懂问我
		vx = (n-b*vy) / a;
		if (vx < 0)		//题目要的是使用砝码的个数,所以要正整数
			vx = -vx;
		/**********②令x是最小正整数解**********/
		x *= n;
		x = (x % b + b) % b;
		y = (n-a*x) / b;
		if (y < 0)		//同理
			y = -y;
		/**********③使得和最小**********/
		if (x + y < vx + vy)
			vx = x, vy = y;
		printf ("%I64d %I64d\n", vx, vy);
	}
	return 0;
}
  • 相关文章
    网友 2012/4/20 11:14:58 发表

    vy = (vy % a a) % a;解释下下

发表评论
用户名: 匿名