首页 > 代码库 > poj 2142 扩展欧几里得
poj 2142 扩展欧几里得
原题实际上就是求方程a*x+b*y=d的一个特解，要求这个特解满足|x|+|y|最小
套模式+一点YY就行了
总结一下这类问题的解法：
对于方程ax+by=c
设tm=gcd(a,b)
先用扩展欧几里得求出方程ax+by=tm的解x0、y0
然后有a*x0+b*y0=tm
令x1=x0*(c/tm)，y1=y0*(c/tm)
则a*x1+b*y1=c
x1、y1即原方程的一个特解
这个方程的通解：xi=x1+k*(b/m)，yi=y1-k*(a/m)
另：如果要求yi的最小非负解？令r=a/tm，则解y2=(y1%r+r)%r
针对本题，求出x1、y1后可以YY一下:
(1)：若x1>0，y1>0，
1.y1-=(a/m)，直到y1<0
2.y1+=(a/m)，直到x1<0
(2)：若x1<0，y1>0
y1-=(a/m)，直到y1<0
易知最优解一定出现在这一咕噜里头，操作的同时更新最优答案即可。
1 #include <iostream> 2 #include <cmath> 3 using namespace std; 4 5 int gcd(int a,int b){ 6 if (b==0) return a; 7 return gcd(b,a%b); 8 } 9 10 int extgcd(int a,int b,int& x,int& y){11 int d=a;12 if (b!=0){13 d=extgcd(b,a%b,y,x);14 y-=(a/b)*x;15 }else{16 x=1;y=0;17 }18 return d;19 }20 21 int main()22 {23 int a,b,d,ax,ay,ans;24 while (cin>>a>>b>>d)25 {26 if (a==0 && b==0 && d==0) break;27 else28 {29 int x,y;30 int tm=extgcd(a,b,x,y);31 int x1=x*(d/tm),y1=y*(d/tm);32 int ra=a/tm,rb=b/tm;33 y1=(y1%ra+ra)%ra;34 x1=(d-y1*b)/a;35 int x2=x1,y2=y1;36 ans=abs(x2)+abs(y2);37 ax=x2; ay=y2;38 if (x2<0)39 {40 while (y2>0)41 {42 y2-=ra; x2+=rb;43 if ((abs(y2)+abs(x2))<ans)44 {45 ans=abs(y2)+abs(x2);46 ax=x2; ay=y2;47 }48 }49 }50 else if (x2>0)51 {52 while (y2>0)53 {54 y2-=ra; x2+=rb;55 if ((abs(y2)+abs(x2))<ans)56 {57 ans=abs(y2)+abs(x2);58 ax=x2; ay=y2;59 }60 }61 x2=x1; y2=y1;62 while (x2>0)63 {64 y2+=ra; x2-=rb;65 if ((abs(y2)+abs(x2))<ans)66 {67 ans=abs(y2)+abs(x2);68 ax=x2; ay=y2;69 }70 }71 }72 cout<<abs(ax)<<" "<<abs(ay)<<endl;73 }74 }75 return 0;76 }
poj 2142 扩展欧几里得
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。