题意：两个青蛙在赤道上跳跃，走环路。起始位置分别为x，y。每次跳跃距离分别为m，n。赤道长度为L。两青蛙跳跃方向与次数相同的情况下，问两青蛙是否有方法跳跃到同一点。输出最少跳跃次数。
分析：扩展欧几里德。设两青蛙跳了s步。有方程：(x+n*s)-(y+m*s)=k*L。整理得：(n-m)*s+L*(-k)=y-x
此时方程已经符合扩展欧几里德的形式:a*x+b*y=gcd(a,b)了。按要求求解即可。
扩展欧几里德算法：
扩展欧几里德算法我们可以简单的理解为求关于x，y的方程a*x+b*y=gcd(a,b)的一组整数解。用算法模板只能求出一组解，而此方程有数穷多解。设其一组特解为x0,y0。则其通解形式为：x=x0-t*b/g，y=y0+t*a/g。
其中g表示gcd(a,b)。t是一个用来协调x和y同步变化的变量。
该算法同样可用于求解a*x+b*y=c的形式的方程。方法是先求解a*x+b*y=gcd(a,b)。然后两端同时除以gcd(a,b)再乘以c即可整理出原方程的解。即a*(x*c/g)+b*(y*c/g)=c。该方程有解的条件是c能被gcd(a,b)整除。
扩展欧几里德是在欧几里德算法基础上加入了一些东西。gcd(a,b)=gcd(b,a%b) => a*x1+b*y1 = b*x2 + a%b*y2 => x1=y2; y1=x2-[a/b]*y2;
也就是原来的欧几里德在递归过程中值削减方程右侧，而扩展欧几里德要同时对左侧进行变化以求解。递归到最底层时有：b=0,gcd(a,b)=a; x=1,y=0;
#includeusing namespace std;long long abs(long long a){ if (a < 0) return -a; return a;}long long gcd(long long a, long long b){ if (b != 0) return gcd(b, a % b); return a;}void gcdExtend(long long a,long long b,long long d,long long &x,long long &y){ if(!b) {d=a;x=1;y=0;return;} gcdExtend(b,a%b,d,y,x); y-=a/b*x;}long long work(long long a, long long b, long long n){ long long d, minx, x1, y1; d = gcd(a,b); if (n % d != 0) return -1; gcdExtend(a, b, d, x1, y1); minx = (n * x1 / d) % (b / d); if (minx < 0) minx += (b / d); return minx;}void swap(long long &x, long long &y){ long long t; t = x; x = y; y = t;}int main(){ long long x, y, m, n, L, ans, a;// freopen("t.txt", "r", stdin); scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&L); if (m < n) { swap(m, n); swap(x, y); } a = y - x; if (a < 0) a += L; ans = work(m - n, L, a); if (ans == -1) printf("Impossible\n"); else printf("%d\n", ans); return 0;}