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

谁能告诉我,我wa哪了?用拓展欧几里德敲的

Posted by zry918 at 2011-10-15 21:07:38 on Problem 2142
#include<stdio.h>
#include<math.h>
#include<iostream>

using namespace std;

void swap(int &a,int &b)
{
	 int t=a;
	 a=b;
	 b=t;
}
int exgcd(int a,int b,int &x,int &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	int g=exgcd(b,a%b,x,y);
	int t=x;
	x=y;
	y=t-a/b*x;
	return g;
} 
int getxx(int t,int x,int b)
{
	return fabs(x+t*b);
}
int getyy(int t,int y,int a)
{
	 return fabs(y-t*a);
}
int getaxby(int x,int y,int a,int b,int t)
{
	return a*getxx(t,x,b)+b*getyy(t,y,a);
}
int getxy(int x,int y,int a,int b,int t)
{
	return getxx(t,x,b)+getyy(t,y,a);
}
int main()
{
	int a,b,c,x,y,xx,yy,t,g,t1,t2;
    bool  flag;
	while(scanf("%d%d%d",&a,&b,&c)!=EOF&&a||b||c)
	{	
		if(a==b)
		{
			c=c/a;
			b=1;
			a=1;
		}                 //这句话去掉也是一样wa
		flag=false;
		if(a<b)
		{
			swap(a,b);
			flag=true;
		}
		g=exgcd(a,b,x,y);

		a=a/g;
		b=b/g;

        x*=c/g;
		y*=c/g;	

		t1=y*g/(a*g);

//		printf("x=%I64d y=%I64d t1=%I64d %I64d\n",x,y,t1,g);

		if(t1*a/g-y>=0)t1--;
		t2=t1+1;
//		printf("t1,t2=%I64d,%I64d\n",t1,t2);
		if(getxy(x,y,a,b,t1)>getxy(x,y,a,b,t2))
		{
			t=t2;
		}
		else if(getxy(x,y,a,b,t1)<getxy(x,y,a,b,t2))
		{
			t=t1;
		}
		else
		{
			if(getaxby(x,y,a,b,t1)>getxy(x,y,a,b,t2))
				t=t2;
			else
				t=t1;
		}
		xx=getxx(t,x,b);
		yy=getyy(t,y,a);
		if(flag)
			printf("%d %d\n",yy,xx);
		else
			printf("%d %d\n",xx,yy);


	}
	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