| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
那位大虾帮忙看看呀?总是Runtime Error!#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator