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