首页 > 代码库 > POJ 2142 - The Balance [ 扩展欧几里得 ]
POJ 2142 - The Balance [ 扩展欧几里得 ]
题意：
给定 a b n找到满足ax+by=n 的x，y 令|x|+|y|最小（等时令a|x|+b|y|最小）
分析：
算法一定是扩展欧几里得。
最小的时候一定是 x 是最小正值 或者 y 是最小正值
(简单的证明应该是分x,y 符号一正一负，和x,y符号都为正来考虑)
扩欧解的方程为 ax+by = gcd(a, b)
先简化问题，等价为扩欧求的是 a‘x+b‘y = 1
则原方程等价为 a‘x+b‘y = n‘ (a, b, n 全部除以gcd(a, b) )
先解x为最小正值的时候
x = (x % b‘ + b‘) % b‘
此时y = (n‘ - x*a) / b
考虑 y时同理。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 int abs(int x) 6 { 7 return x > 0 ? x : -x; 8 } 9 int ExtGcd(int a, int b, int& x, int& y)10 {11 if (b == 0) { x = 1; y = 0; return a;}12 int d = ExtGcd(b, a%b, y, x);13 y -= a/b*x;14 return d;15 }16 int a, b, d;17 int main()18 {19 while (~scanf("%d%d%d", &a, &b, &d) && (a+b+d))20 {21 int x, y;22 int gcd = ExtGcd(a, b, x, y);23 a /= gcd;//简化问题 24 b /= gcd;25 d /= gcd;26 x *= d;27 x = (x%b+b) % b;//x大于0的最小值 28 y = (d-x*a) / b;//对应 y 29 int ans1 = abs(x), ans2 = abs(y);30 y = (y%a+a) % a; 31 x = (d-y*b) / a;32 int x0 = abs(x);33 int y0 = abs(y);34 if (x0+y0 < ans1+ans2 ) ans1 = x0, ans2 = y0;35 else if (x0+y0==ans1+ans2 && a*x0+b*y0 < a*ans1+b*ans2) ans1 = x0, ans2 = y0;36 printf("%d %d\n", ans1, ans2);37 }38 }39 //
POJ 2142 - The Balance [ 扩展欧几里得 ]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。