| ||||||||||
| 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 | |||||||||
不明白为什么WA,用扩展欧机里辗转相除法做的,标准的ax=b(mod m)的解法,谁能帮看看。。。。。谢谢了// 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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator