首页 > 代码库 > POJ 2142:The Balance_扩展欧几里得(多组解)

POJ 2142:The Balance_扩展欧几里得(多组解)

 

先做出两个函数的图像,然后求|x|+|y|的最小值。|x|+|y|=|x0+b/d *t |+|y0-a/d *t| 这个关于t的函数的最小值应该在t零点附近(在斜率大的那条折线的零点附近,可以观察出来)。以下三种情况中,函数最小值都应该出现在B点附近。

/*
对于不定整数方程xa+yb=c,若 c mod Gcd(a, b)=0,则该方程存在整数解,否则不存在整数解。上面已经列出找一个整数解的方法,在找到x * a+y * b = Gcd(a, b)的一组解x0,y0后,/*x * a+y * b = Gcd(a, b)的其他整数解满足:x = x0 + b/Gcd(a, b) * ty = y0 - a/Gcd(a, b) * t(其中t为任意整数)至于xa+yb=c的整数解,只需将x * a+y * b = Gcd(a, b)的每个解乘上 c/Gcd(a, b) 即可在找到x * a+y * b = Gcd(a, b)的一组解x0,y0后,应该是得到x * a+y * b = c的一组解x1 = x0*(c/Gcd(a,b)),y1 = y0*(c/Gcd(a,b)),x * a+y * b = c的其他整数解满足:x = x1 + b/Gcd(a, b) * ty = y1 - a/Gcd(a, b) * t(其中t为任意整数)x 、y就是x * a+y * b = c的所有整数解。*/#include<stdio.h>#include<math.h>#include<limits.h>int ext_gcd(int a,int b,int &x,int &y){ if(b==0) { x=1;y=0; return a; } int temp=ext_gcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; return temp;}int main(void){ int a,b,x,y,i,j,n,k; while(scanf("%d%d%d",&a,&b,&k)!=EOF&&(a|b|k)) { int flag=0; if(a<b){ int temp=a;a=b;b=temp;flag=1; } int gcd=ext_gcd(a,b,x,y); int x0=x*(k/gcd); int y0=y*(k/gcd); int h=y0/(a/gcd);//|y0 - a/gcd * i|=0-->y0/(a/gcd)=i int min=INT_MAX,minx,miny; for(i=h-2;i<h+3;i++) { x = x0 + b/gcd * i; y = y0 - a/gcd * i; if(abs(x)+abs(y)<min){ min=abs(x)+abs(y);minx=x;miny=y; } } if(!flag) printf("%d %d\n",abs(minx),abs(miny)); else printf("%d %d\n",abs(miny),abs(minx)); } return 0;}

 

POJ 2142:The Balance_扩展欧几里得(多组解)