记录编号	555616	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	[POJ 1061] 青蛙的约会	最终得分	100
用户昵称	Oasiz	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2020-10-09 20:20:36	内存使用	0.00 MiB

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
ll x,y,m,n,l,A,B,xx,yy;
ll exgcd(ll a,ll b,ll &x1,ll &y1){
	if(b==0){
		x1=1;
		y1=0;
		return a;
	}
	int r=exgcd(b,a%b,x,y1);
	int t=x1;
	x1=y1;
	y1=t-a/b*y1;
	return r;
}
int main(int argc, char** argv){
	freopen("poj_hama.in","r",stdin);
	freopen("poj_hama.out","w",stdout);
	cin>>x>>y>>m>>n>>l;
	A=n-m;
	B=x-y;
	if(A<0){
		A=-A;
		B=-B;
	}
	ll ans=exgcd(A,l,xx,yy);
	if(B%ans!=0){
		cout<<"Impossible";
	}
	else{
		int k=(xx*(B/ans))%(l/ans);
		if(k<0){
			k+=l;
		}
		cout<<k;
	}
	return 0;
}