| ||||||||||
| 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 | |||||||||
为什么你不首先怀疑你自己错了?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