Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
ACM ICPC 2018 World Finals

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

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator