AC链接：http://poj.org/problem?id=1061
参考：
http://blog.csdn.net/loi_dqs/article/details/49488851
http://blog.renren.com/share/341541251/14518239244/0
解析：
线性同余方程
同余方程即：ax≡b(mod m)，a、b、m都是整数，求解x。
上面的表达式也就是(ax-b)modm=0
求解原理：
对于ax≡b(modm)，存在ax+by=gcd(a,b)，x、y是整数。
1、gcd(a,b)=gcd(b,a mod b)
2、有ax+by=gcd(a,b)=gcd(b,a mod b)
而gcd(b,a mod b)=bx'+(amod b)y'=ay'+b(x'-a div b*y')//最后等号一步就是打开括号整理
从而ay'+b(x'-a divb*y')=ax+by
所以可以得到x=y', y=x'-adiv b*y'
3、求解ax≡b(mod m)，就可以在递归的时候由x、y堆砌求到
并且我们知道，a、b不全为0，令a>b,当b=0时，gcd(a,b)=a，此时解为x=1，y=0。
这是递归求解的最底层，是无数解当中的最小解。
对于一个式子ax+by=n，如果gcd(a,b) mod n≠0,便不存在整数解x，y。
对于本题：
我们可以设在两只青蛙跳了s次之后相遇。则方程为：(x+m*s)-(y+n*s)=k*L(k=0,1,2....);
可以化解为(n-m)*s+k*L=x-y; （公式一）
我们令a=n-m，b=L，c=x-y;
可以得到式子a*s+b*k=c(这里的s，k就相当于上面线性同余方程的x，y)我们要求的便是这个s值。
但我们用扩展欧几里得算法算的是方程(n-m)*s’+k’*L=gcd(n-m,L)（公式二）的解(s’,k’)，想要得到s只需联立两个公式得s=s’*(x-y)/gcd(n-m,L),
（按照扩展欧几里得算法我们得到s’代表一个解系，那么s也是代表一个解系，我们需要在其中找到最小解。）
进一步得到题目答案即最小解：s=[s’*(x-y)/gcd(n-m,L)]%(L/ gcd(n-m,L))
这里进一步的证明如下：
设要解的方程（求x）是：
而我们已经解得
此时将第二个方程左右同时乘c/d，则可得：
所以：
这样并没有完，因为这只是一组解，我们要求最小正整数解。
我们知道：若一组 < x,y > 是ax+by=c的一组解，那么
也是原方程的一组解。
这样我们只需要让解得的x不断减b/d，直到再减就为负数时，所得的x就是我们要的解。
其实这个过程就是模运算，所以最小正整数解就是：
还有一种证法。对于这个式子：
我们可以让等式两边同时除以d，则：
相当于化简，此时对结果无影响，求就好了。
由于x≠y显然当n==m是无解，如果c mod gcd(a,b)≠0（即(x-y) mod gcd(n-m,L)≠0）也无解，输出'Impossible'(无整数解)
代码：
#include<iostream> #include<string> #include<cstdio> #include<algorithm> #include<cmath> #include<iomanip> #include<queue> #include<cstring> #include<map> using namespace std; typedef long long ll; ll n,m,x,y,L; ll extend_Euclide(ll a,ll b,ll &x,ll &y) {if(b==0){x=1; y=0;return a;}ll t=extend_Euclide(b,a%b,x,y);ll temp=x;x=y;y=temp-(a/b)*y;return t; }int main() {ll res,ans,tmp;while(scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&L)!=EOF){if(m==n){printf("Impossible\n");continue;}ll gcd=extend_Euclide(n-m,L,res,tmp); //解方程(n-m)*s+k*L=gcd(n-m,L),这里gcd就是gcd(n-m,L)，res就是s，tmp就是k，（s，k）是一组解if((x-y)%gcd){printf("Impossible\n");}else{ll mod=L/gcd;ans=(res*(x-y)/gcd%mod+mod)%mod;//求最小解printf("%lld\n",ans);}}return 0; }