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

dsds

Posted by ouwenbo at 2015-05-24 10:00:15 on Problem 2142
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(a==0)
	{
		x=0;y=1;
		return b;
	}
	else
	{
		ll tx,ty;
		ll d=exgcd(b%a,a,tx,ty);
		x=ty-(b/a)*tx;
		y=tx;
		return d;
	}
}
int main()
{
	ll A,B,K,x,y,d,a,b,c,ax,ay,ans,X,Y;
	while(scanf("%I64d%I64d%I64d",&a,&b,&c)!=EOF)
	{
		if(a==0 && b==0 && c==0) break;
		ans=9999999999;
		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) && 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){ans=X+Y;ax=X;ay=Y;}
	    }
	    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) && 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){ans=X+Y;ax=X;ay=Y;}
	    }
	    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) && 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){ans=X+Y;ax=X;ay=Y;}
		}
		if(ans!=99999999999)printf("%I64d %I64d\n",ax,ay);
		else printf("no solution\n");
	}
	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