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

=。=秒过

Posted by huangzhengdoc at 2015-05-24 10:04:57 on Problem 2142 and last updated at 2015-05-24 10:05:15
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
LL exgcd(LL a,LL b,LL &x,LL &y)
{
    LL ret;
	if(a==0)
	{
	    x=0;y=1;
	    return b;
    }
    else
    {
    	LL tx,ty;
        ret=exgcd(b%a,a,tx,ty);
		x=ty-b/a*tx;
		y=tx;
		return ret;	
    }
}
int main()
{
	LL a,b,c,A,B,K,d,x,y,ax,ay,X,Y;
	while(scanf("%I64d%I64d%I64d",&a,&b,&c)!=EOF)
	{
		if(a==0&&b==0&&c==0)return 0;
		LL ans=0x7FFFFFFFFFFFFFFF;
		/* Ax+By=K */
		A=a;B=b;K=c;
		d=exgcd(A,B,x,y);
		if(K%d==0)
		{
		    X=(x*(K/d)%(B/d)+B/d)%(B/d);
			Y=(K-A*X)/B;
			if(ans>(X+Y)&&X>=0&&Y>=0)
			{
			    ans=X+Y;
			    ax=X;
			    ay=Y;
		    }
		    Y=(y*(K/d)%(A/d)+A/d)%(A/d);
			X=(K-B*Y)/A;
			if(ans>(X+Y)&&X>=0&&Y>=0)
			{
			    ans=X+Y;
			    ax=X;
			    ay=Y;
		    }
		}
		/* Ax=K+By > Ax-By=K*/
		A=a;B=b;K=c;
		d=exgcd(A,B,x,y);
		if(K%d==0)
		{
		    X=(x*(K/d)%(B/d)+B/d)%(B/d);
			Y=(A*X-K)/B;
			if(ans>(X+Y)&&X>=0&&Y>=0)
			{
			    ans=X+Y;
			    ax=X;
			    ay=Y;
		    }
		    Y=(y*(K/d)%(A/d)+A/d)%(A/d);
			X=(K-B*Y)/A;
			if(ans>(X+Y)&&X>=0&&Y>=0)
			{
			    ans=X+Y;
			    ax=X;
			    ay=Y;
		    }
		}
		/* By-Ax=K */
		A=a;B=b;K=c;
		d=exgcd(A,B,x,y);
		if(K%d==0)
		{
		    X=(x*(K/d)%(B/d)+B/d)%(B/d);
			Y=(K+A*X)/B;
			if(ans>(X+Y)&&X>=0&&Y>=0)
			{
			    ans=X+Y;
			    ax=X;
			    ay=Y;
		    }
		    Y=(y*(K/d)%(A/d)+A/d)%(A/d);
			X=(B*Y-K)/A;
			if(ans>(X+Y)&&X>=0&&Y>=0)
			{
			    ans=X+Y;
			    ax=X;
			    ay=Y;
		    }
		}
		if(ans==0x7FFFFFFFFFFFFFF)printf("no solution\n");
		else printf("%I64d %I64d\n",ax,ay);
	}
    return 0;	
}

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