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

Re:我用同余方程,怎么错了?看了个过了的程序,和他不一样的数据,我觉得他错了。

Posted by bieleyingshikong at 2008-07-15 15:13:17 on Problem 1061
In Reply To:我用同余方程,怎么错了?看了个过了的程序,和他不一样的数据,我觉得他错了。 Posted by:chengmingvictor at 2005-08-08 11:43:37
> #include <iostream>
> using namespace std;
> 
> 
> long long extended_gcd(long long a, int b, long long &x, long long &y) // a > 0, b > 0
> {//方程a * x + b * y = d 中的各个变量的求解
> 	if(b == 0)
> 	{
> 		x = 1;
> 		y = 0;
> 		return a;
> 	}
> 	
> 	long long t1 = extended_gcd(b, a % b, x, y);
> 	long long t2 = x;
> 	x = y; 
> 	y = t2 - (a / b) * y;
> 	return t1;
> }
> 
> //解系x0 + k * m / d  
> bool equation_modular(long long a, long long b, long long m, long long &d, long long &x0)
> {
> 	long long x, y;
> 	d = extended_gcd(a, m, x, y);
> 	if(b % d != 0)
> 		return false;  //没有解
> 
> 	x0 = x * (b / d) % m;
> 	x0 = (x0 + m) % m;
> 	return true;
> }
> 
> int main()
> {
> 	long long x, y, m, n, L;
> 	while(cin>>x>>y>>m>>n>>L)
> 	{
> 		long long a = m - n;
> 		long long b = y - x;
> 		if(a == 0)
> 		{
> 			cout<<"Impossible"<<endl;
> 			return 0;
> 		}
> 
> 		if(a < 0)
> 		{
> 			a = -a;
> 			b = -b;
> 		}
> 
> 		b = b % L;
> 		b = (b + L) % L; 
> 
> 		long long d, x0;
> 		if(equation_modular(a, b, L, d, x0)) //在解系中找一个(0,L)间最小的
> 		{
> 			int result = L - x0 - 1;
> 			result = result / double (L / d); 
> 			result = (x0 + result * (L / d)) % L;
> 			cout<<result<<endl;
> 		}
> 		else
> 			cout<<"Impossible"<<endl;
> 	}
> 	return 0;
> } 
> 程明明 11:22:00
> 我用同余方程解的 
> 程明明 11:22:40
> 我也找了个过了的程序:
> #include <fstream>
> using namespace std;
> ifstream cin("working.in");
> ofstream cout("working.out");
> 
> int main()
> {  
> 	unsigned long x,y,m,n,l;
> 	while(cin>>x>>y>>m>>n>>l)
> 	{
> 		if (m == n) 
> 			cout<<"Impossible\n";
> 		else
> 		{ 
> 			if(m > n)
> 			{
> 				m = m - n;
> 				x = (y - x + l) % l;
> 			}
> 			else 
> 			{
> 				m = n - m;
> 				x = (x - y + l) % l;
> 			}  //把其中移动比较慢的那个当做不动。
> 			n = x / m;
> 			x = x % m;
> 			y = x;                      //  用相对运动的思想。
> 			while(1)
> 			{ 
> 				if(y==0) 
> 				{
> 					cout<<n<<endl;
> 					break;
> 				} // 当两个人的距离等于零时
> 				n = n + (y + l) / m;
> 				y = (y + l) % m;                         
> 				if(y == x) 
> 				{
> 					cout<<"Impossible\n";
> 					break;
> 				} //当两个人的距离又回到
> 			}                                                           //原来的距离表示不可能
> 		}
> 	}
> 	return 0;
> }
>  
> 程明明 11:25:03
> 我找了几组测试数据,当l 比x,y 都大时和这个程序运行结果相同。l较小时就不同了。他的程序中x = (y - x + l) % l;对这种情况处理结果我认为是错的 
> 程明明 11:25:51
> 但他的过了我的WA了 
> 程明明 11:26:21

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