嗯...

 

题目链接：http://poj.org/problem?id=1061

 

两只青蛙相遇时肯定满足：x+k*m≡y+k*n(mod L)

　　　　　　　　　　　　x+k*m-(y+k*n)=L*s

　　　　　　　　　　　　k*(n-m)-s*L=x-y

 

即把模线性方程变形后a*x+b*y=c，用exgcd求解，

先ax+by=gcd(a,b)

判断c整除g

然后解就是(x+k*b/g) ,(y-k*a/g)

注意答案要求非负，所以要进行处理...

 

AC代码：

1 #include
        
          2 #include
         
           3  4 using namespace std; 5  6 inline void exgcd(long long a, long long b, long long &g, long long &x, long long &y){ 7     if(!b) { g = a; x = 1; y = 0;} 8     else { exgcd(b, a % b, g, y, x); y -= x * (a / b);}  9 }10 11 int main(){12     long long xx, yy, l, m, n, a, b, c, g, x, y;13     scanf("%lld%lld%lld%lld%lld", &xx, &yy, &m, &n, &l);14     a = n - m; b = l; c = xx - yy;15     exgcd(a, b, g, x, y);//(n-m) * x + l * y = xx - yy 16     if(c % g) printf("Impossible\n");17     else{18         c /= g; b /= g;19         printf("%lld\n", (x % b * c % b + b) % b);//处理非负 20     }21     return 0;22 }