记录编号	581596	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	[POJ 1061] 青蛙的约会	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2023-08-07 15:40:50	内存使用	0.00 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long L;
L x,y,m,n,l,gcd,xx,yy;
inline L exgcd(L a,L b,L &x,L &y){
	if(!b){x=1;y=0;return a;}
	L gcd(exgcd(b,a%b,x,y)),tmp(x);
	x=y;y=tmp-a/b*y;return gcd;
}
int main(){
	freopen("poj_hama.in","r",stdin);freopen("poj_hama.out","w",stdout);
	scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l);
	gcd=exgcd(l,m-n,xx,yy);//cout<<l<<' '<<m-n<<' '<<xx<<' '<<yy<<' '<<gcd<<' '<<y-x<<endl;
	if((y-x)%gcd){puts("Impossible");return 0;}
	yy=yy*(y-x)/gcd;//cout<<l<<' '<<gcd<<' '<<l/gcd<<endl;
	// if(l/gcd>0){
	// 	while(yy>0)yy-=l/gcd;
	// 	while(yy<0)yy+=l/gcd;
	// }
	// else{
	// 	while(yy>0)yy+=l/gcd;
	// 	while(yy<0)yy-=l/gcd;
	// }
	L delta(abs(l/gcd));
	if(yy<0){
		yy=delta-(-yy)%delta;
		// yy=yy+((-yy-1)/delta+1)*delta;
	}
	else{
		yy=yy%delta;
		// yy=yy-(yy/delta)*delta;
	}
	printf("%lld",yy);
}