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

没道理的事啊~1061

Posted by tryhard at 2006-04-24 17:04:51
我用了数论的解不定方程的方法怎么就是做不出来的呢?
什么原因呢


#include<iostream.h>

#define DS_N 0
#define DS_P 1

typedef struct
{
	long x;
	long y;
} ANSWER;

long gcd(long a,long b)
{
	if(a%b==0)
		return b;
	if(b%a==0)
		return a;

	return a>b?gcd(a%b,b):gcd(a,b%a);
}

ANSWER exgcd(long a,long b)
{
	ANSWER rst,buf;
	if(a==1)
	{
		rst.x=1;
		rst.y=0;
		return rst;
	}
	if(b==1)
	{
		rst.x=0;
		rst.y=1;
		return rst;
	}

	if(a>b)
	{
		buf=exgcd(a%b,b);
		rst.y = buf.y-(a/b)*buf.x;
		rst.x =	buf.x;
		return rst;

	}
	else
	{
		buf	=exgcd(a,b%a);
		rst.x =buf.x-(b/a)*buf.y;
		rst.y =buf.y;
		return rst;
	}

}

main()
{
	long sa,sb,va,vb,l;

	long ds,dv,times;	
	short statu=0;

	long a,b,c1;
	long b1;
	long g;


	cin>>sa>>sb>>va>>vb>>l;

	if(va>vb)
	{
		dv=vb-va;
		ds=sb-sa;
	}
	else if(va==vb)
	{
		cout<<"Impossible";
		return 0;
	}
	else 
	{
		dv=va-vb;
		ds=sa-sb;
	}

	if(ds>=0)
		statu=DS_P;
	else
	{
		statu=DS_N;
		ds=-ds;
	}

	g=gcd(-dv,l);
	if(ds%g!=0)
	{
		cout<<"Impossible";
		return 0;
	}

	a=(-dv)/g;
	b=l/g;

	c1=ds/g;
	
	ANSWER rst=exgcd(a,b);
	rst.x *= c1;
	rst.y *= c1;

	if(statu==DS_P)
	{
		if(rst.x>0)
			times=rst.x%b;
		else	times=rst.x%b+b;
	}
	else
	{
		if(rst.x>0)
			times=-(rst.x%b-b);
		else	times=-rst.x%b;
	}
	cout<<times;
	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