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

第一次扩展欧几里得 oms AC

Posted by Heng_Xing at 2011-07-12 12:12:30 on Problem 1061
#include<stdio.h>
int gcd(int a,int b)
{
	if(b==0)
		return a;
	else
		return gcd(b,a%b);
}
void extend_gcd(int a,int b,__int64 &x,__int64 &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return ;
	}
	else
	{
		extend_gcd(b,a%b,x,y);
		__int64 temp=x;
		x=y;
		y=temp-a/b*y;
	}
}
int main (void)
{
	int x,y,m,n,l;
	__int64 x1,y1;
	int a,b,c;
	int temp;
	while(scanf("%d %d %d %d %d",&x,&y,&m,&n,&l)!=EOF)
	{
		a=m-n;
		b=l;
		temp=b;
		c=y-x;
		int r=gcd(a,b);
	//	printf("%d\n",r);
		if(c%r)
			printf("Impossible\n");
		else
		{
			extend_gcd(a,b,x1,y1);
			//	printf("%d\n",r);
			//	printf("%d %d %d %d %d\n",a,b,c,x1,y1);
			__int64 t=(c*x1/r)/b;
			x1=c*x1/r-b*t;
			if(x1<0)
				x1+=b;
			printf("%I64d\n",x1);
		}
	}
	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