青蛙的约会(扩展欧几里德).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
// 如果GCD(a,b) = d, 则存在x, y, 使d = ax + by
// extended_euclid(a, b) = ax + by
__int64 extended_euclid(__int64 a, __int64 b, __int64 &x, __int64 &y) {
	__int64 d;
	if(b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	d = extended_euclid(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

int main() {
	__int64 x, y, m, n, L;
	__int64 a, b, gcd, A, B;
	while(scanf("%I64d %I64d %I64d %I64d %I64d", &x,&y,&m,&n,&L)==5) {
		A = m - n;
		B = y - x;
		if(A < 0) {
			A = -A;
			B = -B;
		}
		gcd = extended_euclid(A,L,a,b);
		if(m == n || B%gcd != 0) puts("Impossible");
		else {
			__int64 mul = B / gcd;
			__int64 t = mul * a;
			__int64 s = L / gcd;
			printf("%I64d\n", (t%s +s)%s);
		}
	}
}