解题报告：luogu P1516 青蛙的约会

题目链接：P1516 青蛙的约会
考察拓欧与推式子(qwq)。
题意翻译?
求满足

的最小整数解(d)。
我们设（以下均满足(ngeqslant m)）：

两式相减，即得：

这样我们就把不确定的(t)消掉了！
我们再把它转化成模(l)意义的 :

扩欧解方程即可，无解即为(Impossible)。
时间复杂度是(O(logn))，可以通过本题。

(Code):

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
long long l,x,y,m,n;
inline void exgcd(ll a,ll b)
{
	if(b==0)
	{
		x=1,y=0;
		return;
	}
	exgcd(b,a%b);
	ll t=x;
	x=y;
	y=t-a/b*y;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
void solve(ll a,ll b,ll c)
{
	ll g=gcd(a,b);
	if(c%g!=0)
	{
		printf("Impossible
");
		return;
	}
	a/=g,b/=g,c/=g;
	exgcd(a,b);
	x=x*c;
	x=(x%b+b)%b;
	printf("%lld
",x);
}
int main()
{
	scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l);
	if(n<m) swap(x,y),swap(m,n);
	solve((n-m)%l,l,(x-y+l)%l);
	return 0;
}