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

那位大虾帮忙看看呀?总是Runtime Error!

Posted by percysuper at 2007-03-24 20:27:26 on Problem 1061
#include <iostream>
using namespace std;


long gcd( long a, long b ) //求两个数的最大公约数
{
	if ( a < b )
	{
		a = a + b;
		b = a - b;
		a = a - b;
	}
	if ( a % b == 0 )
		return b;
	else 
	{
		long c;
        for(c =  a % b ; c > 0  ; c = a % b)
        {
            a = b;
            b = c;
        }
        return b;
	}	
}

long    gcd(long    a,    long    b    ,    long&    ar,long    &    br) //扩展欧几里得算法
 {
  long    x1,x2,x3;
  long    y1,y2,y3;
  long    t1,t2,t3;
  if(0    ==    a)
  {//有一个数为0,就不存在乘法逆元
               ar    =    0;
               br    =    0    ;
               return    b;
  }
  if(0    ==    b)
  {
               ar    =    0;
               br    =    0    ;
               return    a;
  }
  x1    =    1;
  x2    =    0;
  x3    =    a;
  y1    =    0;
  y2    =    1;
  y3    =    b;
  long    k;
  for(    t3    =    x3    %    y3    ;    t3    !=    0    ;        t3    =    x3    %    y3)
  {
   k    =    x3    /    y3;
   t2    =    x2    -    k    *    y2;
   t1    =    x1    -    k    *    y1;
   x1    =    y1;
   x2    =    y2;
   x3    =    y3;
   y1    =    t1;
   y2    =    t2;
   y3    =    t3;
  }
  if(    y3    ==    1)
  {
   //有乘法逆元
   ar    =    y1;
   br    =	  y2;
   return    1;
  }else{
          //公约数不为1,无乘法逆元
           ar    =    0;
           br    =    0;
           return    y3;
  }
 }

int main()
{
	long x;    //青蛙A坐标
	long y;	   //青蛙B坐标
	long m;    //青蛙A一次能向西跳的距离
	long n;	   //青蛙B一次能向西跳的距离
	long L;	   //纬线长度
	bool flag = true; //是否能约会的标记

	cin >> x >> y >> m >> n >> L;
	
	y = ( y - x + L ) % L;
	n = ( n - m + L ) % L;
	
	long divisor = gcd( n, L );
	if ( y % divisor != 0 )
	{
		cout << "Impossible" << endl;
		return 0;
	}
	
	L = L / divisor;
	y = y / divisor;
	n = n / divisor;
	
	long j;
	long k;
	gcd( L, n, j, k );
	cout << ( -y * k + L ) % 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