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,用扩展欧机里辗转相除法做的,标准的ax=b(mod m)的解法,谁能帮看看。。。。。谢谢了

Posted by letaotao at 2007-06-21 15:29:39 on Problem 1061
// 1061.cpp : 定义控制台应用程序的入口点。
//

#include <iostream>
#include <math.h>

using namespace std;

typedef long long BigInt ;

BigInt x , y , m , n , L;

template <class Type>
Type babs(Type in)
{
	return (in > 0)? in : -in;
}

template <class Type>
Type Eucliead_Ext(Type a , Type b , Type& x , Type& y)
{
	Type gcd;
	if(b == 0)
	{
		x = 1;
		y = 0;
		return a;
	}
	else
	{
		gcd = Eucliead_Ext(b , a % b , x , y);
		Type t = x; 
		x = y;
		y = t - (a/b)*y; 
	}
	return gcd;
}

//solve the function ax=b(mod n) , please make sure that a >=b and b % gcd(a , b) == 0
template <class Type>
Type GetResult(Type a , Type b , Type n) 
{
	Type result , gcd , x , y , wa , wb , temp;
	bool exchanged = false;
	wa = a;
	wb = n;
	if(wb > wa)
	{
		exchanged = true;
		temp = wb;
		wb = wa;
		wa = temp;
	}
	gcd = Eucliead_Ext(wa , wb , x , y);
	Eucliead_Ext(wa/gcd , wb/gcd , x , y);

	if(exchanged)
		result = y;
	else
		result = x;
	result *= (b) / gcd;
	if(result < 0)
	{
		if(babs(result) % (n / gcd) == 0)
			result = 0;
		else
			result += (b / gcd) *(n / gcd + 1) * (n / gcd);
	}
	return result;
}

int main(int argc, char* argv[])
{
	BigInt distance , x1 , x2;
	while(cin >> x >> y >> m >> n >> L)
	{
		BigInt wx , wy , wm , wn , wmnSub , wxySub;
		wmnSub = babs(m - n);
		if(n > m)
		{
			wxySub = x - y;
		}
		else
		{
			wxySub = y - x;
		}
		if(wxySub < 0)
		{
			wxySub += L;
		}

		BigInt result = Eucliead_Ext(wmnSub , L  , x1 , x2); 

		if(wxySub % result != 0)
		{
			cout << "Impossible" << endl;
		}
		else
		{
			cout << GetResult(wmnSub , wxySub , L) << endl;
		}
	}
	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