| ||||||||||
| 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