Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

用 ax+by=c 看作一条直线 分成 分段函数 做 范围 一目了然 特简单 根本没用到 扩欧

Posted by 1686231736 at 2018-02-13 01:10:01 on Problem 2142
#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: