首页 > 代码库 > poj 2142 The Balance 扩展欧几里得
poj 2142 The Balance 扩展欧几里得
首先求出通项 X=x+b/d*t Y=y-a/d*t (x,y为ax+by=gcd(a,b)的解,d=gcd(a,b))可知我们要求的最小的解是 abs(x+b/d*t) + abs(y-a/d*t)
设a>b不是的话,就交换a,b,我们发现上述关于t的方程是 |x+k1*t| + |y-k2*t|,由于a>b所以k2>k1,所以方程一开始右边减小的比左边增加的快
所以当y=k2*t的时候,减小的最多(之后右边为负数,两边都递增),所以最小值点在y=k2*t,由于误差,我们要在附近几个点找找。
#include<iostream> #include<cmath> #include<cstdio> using namespace std; typedef long long ll; ll myabs(ll a) { return a>0?a:-a; } void gcd(ll a,ll b,ll& d,ll& x,ll& y) { if(!b) {d=a;x=1;y=0;} else {gcd(b,a%b,d,y,x);y-=x*(a/b);} } ll get(ll x,ll y,ll a,ll b,ll d,ll t) { return myabs(x+b/d*t)+myabs(y-a/d*t); } int main() { ll a,b,c,d,x,y,t1,t2,ans,x1,y1; while(cin>>a>>b>>c&&(a||b||c)) { int f=1; if(a<b) {swap(a,b);f=0;} gcd(a,b,d,x,y); x=x*c/d;y=y*c/d; ll t=d*y/a; ll mins=0x3f3f3f3f3f3fll; for(ll i=t-2;i<=t+2;i++) { ans=get(x,y,a,b,d,i); if(ans<mins) { mins=ans; x1=myabs(x+b/d*i); y1=myabs(y-a/d*i); } } if(f) cout<<x1<<" "<<y1<<endl; else cout<<y1<<" "<<x1<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。