poj The Luckiest number

本文主要是介绍poj The Luckiest number，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

                                     The Luckiest numbe

题目：

    在满足|x| + |y|最小时候，让a*|x| + b*|y|最小。求：|x| + |y|最小值。

算法：

    同余式的求解运用。

    解体步骤：

    1、先用gcd判断是否有解。(c%g == 0有解)

    2、对式子求最简式。a' = a/g ; b' = b/g； c' = c/g;

    3、运用扩展欧几里得求解x,y的值。

    4、判断当x,y分别求得最小正整数解时候的大小。

    5、确定最后答案。

    处理过程中有一些细节: 

    1、对求的x,y并不是正确的x,y值。要x = x * c; y = y * c

    2、保证x或y是正数.(x%b + b)%b \ (y%a + a)%a

    

/*1、|x| + |y|最小2、在1相同的时候a*|x| + b*|y|最小
*/#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;typedef long long LL;LL gcd(LL a,LL b){return b?gcd(b,a%b):a;
}void extgcd(LL a,LL b,LL& d,LL& x,LL& y){if(!b) { d = a; x = 1; y = 0; }else { extgcd(b,a%b,d,y,x); y -= x * (a/b); }
}int main()
{LL a,b,c;while(cin >> a >> b >> c){if(a == 0&&b == 0&&c == 0)break;LL d = gcd(a,b);a /= d; b /= d; c /= d;LL x,y;extgcd(a,b,d,x,y);LL x1,y1,x2,y2;//y 取得最小正整数y1 = y * c;y1 = (y1 % a + a) % a;x1 = (c - b*y1) / a;if(x1 < 0) x1 = -x1;  //砝码个数非负//x取得最小正整数x2 = x * c;x2 = (x2 % b + b) % b;y2 = (c - a*x2) / b;if(y2 < 0) y2 = -y2;if(x1 + y1 < x2 + y2){x = x1; y = y1;}else {x = x2; y = y2;}cout << x << " " << y << endl;}return 0;
}/*
700 300 200
500 200 300
500 200 500
275 110 330
275 110 385
648 375 4002
3 1 10000
0 0 0
*/

这篇关于poj The Luckiest number的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---