Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
用 ax+by=c 看作一条直线 分成 分段函数 做 范围 一目了然 特简单 根本没用到 扩欧#define ll long long main() { cin.tie(0); ios::sync_with_stdio(0); ll a,b,c; while(cin>>a>>b>>c) { if(!a&&!b&&!c)break; ll g=__gcd(a,b); ll ans1,ans2; a/=g;b/=g;c/=g; ll minn=INF,x0=c/a; for(ll x=0;x<=x0;x++) { ll mark=(c-a*x)%b,y=(c-a*x)/b; if(!mark) { if(minn>x+y) { ans1=x,ans2=y; minn=x+y; } } } if(minn!=INF) { cout<<ans1<<" "<<ans2<<endl;continue; } ll x1,y1;ll x2,y2; ll a1,a2; for(ll x=0;;x++) { ll mark=(c+a*x)%b,y=(c+a*x)/b; if(!mark) { x1=x,y1=y;break; } } for(ll x=x0;;x++) { ll mark=(a*x-c)%b,y=(a*x-c)/b; if(!mark) { x2=x,y2=y;break; } } if(x1+y1>x2+y2) a1=x2,a2=y2; else if(x1+y1<x2+y2) a1=x1,a2=y1; else if(x1+y1==x2+y2) { if(a*x1+b*y1<=a*x2+b*y2) a1=x1,a2=y1; else a1=x2,a2=y2; } cout<<a1<<" "<<a2<<endl; } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator