POJ1061 青蛙的约会

题目大意是说，给一根长度为$L$的数轴，有两只青蛙分别从数轴的$x$和$y$位置开始向左跳，第一只青蛙的速度是$m$，第二只青蛙的速度是$n$，问这两只青蛙能否在相同时刻相同地点相遇

设两只青蛙在$t$时刻相遇，那么第一只青蛙的位置是$(mt+x)\ mod\ L$，第二只青蛙的位置是$(nt+y)\ mod\ L$，根据题目要求则要求方程$mt+x\equiv nt+y(mod\ L)$的解$t$

按照同余方程转化为裴蜀方程的证明步骤，我们这里也可以得到

$$ mt+x=Lk_1+p\\ nt+y=Lk_2+p $$

两式相减得$(m-n)t+(x-y)=L(k_1-k_2)$，移项$(m-n)t+Lk=y-x$

$x,y,m,n,L$都是已知的，直接带入线性方程求解即可得到$t$，如果求出的$t$小于0，还需要变换一下求出第一个大于0的解

import java.util.Scanner;

public class Main {
    static long x, y;
    static long exgcd(long a, long b) {
        if (b == 0) {
            x = 1;
            y = 0;
            return a;
        }
        long res = exgcd(b, a % b);
        long x1 = x;
        x = y;
        y = x1 - (a / b) * y;
        return res;
    }

    static long linearEquation(long a, long b, long m) throws Exception {
        long d = exgcd(a, b);
        if (m % d != 0)
            throw new Exception("Impossible");
        long n = m / d;
        x *= n;
        y *= n;
        return d;
    }
    
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int a = cin.nextInt();
        int b = cin.nextInt();
        int m = cin.nextInt();
        int n = cin.nextInt();
        int l = cin.nextInt();
        try {
            long d = linearEquation(m-n, l, b-a);
            l /= d;
            l = l < 0 ? -l : l;
            x = (x % l + l) % l;
            System.out.println(x);
        } catch (Exception e) {
            System.out.println("Impossible");
        }
    }
}