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 |
Re:我用同余方程,怎么错了?看了个过了的程序,和他不一样的数据,我觉得他错了。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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator