拓展gcd详解传送门
思路:设时间为t,则两个青蛙的位置分别为(x+mt)mod L、(y+nt) mod L,相遇即是(x+mt)%L=(y+nt)%L,即(m-n)t+kL=y-x。
OK,现在已经符合ax+by=c的方程了,设a=m-n,b=L,c=y-x,然后套用模板求出特解t的值,注意t>0,所以要用通解公式得出最小正整数

解释<1>
gcd 只对非负整数有意义,所以如果a<0等式两边要同时取负,a,c都要变成相反数;b本来就是正数,不用变也不能变。

解释<2>
利用exgcd,我们可以求解ax+by=g的一个解,然后
等式两边同乘c/g,得a* cx/g+b* cy/g=c

那么,x=cx/g就是ax+by=c中x的一个解

如何由一个解得到其它解呢?有一个恒等式a(x+db)+b(y−da)=c

在保证db,da都是整数的情况下,我们让d最小,就可以得到所有的整数解,那么d=n/g。 (n是一个整数)

如果解出的x>0,那么最小非负整数解等于x mod b/g;否则等于x mod b/g+b/g(这个很好理解,只要满足x大于0,我们通过db来调节x使x最小)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;

ll exgcd(ll a, ll b, ll &x, ll &y)
{
   
	if(b==0)
	{
   
		x=1;y=0;
		return a;
	}
	int r=exgcd(b,a%b,x,y);
	ll temp=y;
	y=x-(a/b)*y;
	x=temp;
	return r;
}

int main()
{
   
	ll x,y,m,n,l,a,b,c,p;
	cin>>x>>y>>m>>n>>l;
	a=m-n;
	b=l;
	c=y-x;
	if(a<0)						//<1>
	{
   
		a=-a;
		c=-c;
	}
	p = exgcd(a,b,x,y);
	if(c%p!=0) {
   
		printf("Impossible\n");
	}
	else{
   
		x=x*c/p;
		ll d=b/p;
		if(x<0)                //<2>
			x=x%d+d;
		else
			x=x%d;
		printf("%lld\n",x);
	}
	return 0;
}