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

discuss里提到的大多数据都通过,但仍是WA,请教高手

Posted by mufeng at 2009-02-21 21:06:41 on Problem 1061
//求解模线性方程

#include<iostream>
using namespace std;

//求a,b最大公约数
//d=ax+by
__int64 gy(__int64 a,__int64 b,__int64 &x,__int64 &y)
{
	__int64 d,temp;
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	d=gy(b,a%b,x,y);
	temp=x;
	x=y;
	y=temp-a/b*y;
	return d;
}

//解方程ax=b(mod n)
__int64 solv(__int64 a,__int64 b,__int64 n)
{
	__int64 d,x,y;
	__int64 x0,i,minx=0;
	d=gy(a,n,x,y);
	if(b%d==0)
	{
		x0=x*(b/d)%n; //x0>=0 or x0<0 
		if(x0>0) x0=x0-n; //make sure x0<0
		minx=x0;
		for(i=1;i<=d-1;i++)
		{
			//解:(x0+i*(n/d)) mod n
			if((minx=(x0+i*(n/d))%n)>=0)
				return minx;//只返回最小正数解
		}
		return minx+n;//if minx<0,return minx+n
		
	}

	return -1;//无解

}

int main()
{
	__int64 x,y,m,n,l,xx;

	scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&l);

//	printf("%I64d%I64d%I64d%I64d%I64d\n",x,y,m,n,l);
	/*
	* (x+t*m)-(y+t*n)=0 (mod l)
		that is: t*(m-n)=y-x (mod l)
	*/
	if(m>n)
		xx=solv(m-n,y-x,l);
	else
		xx=solv(n-m,x-y,l);

	if(xx>=0)
		printf("%I64d\n",xx);
	else 
		printf("Impossible\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