pku1061.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>

__int64 e_gcd(__int64 a, __int64 b, __int64 *x, __int64 *y)
{
	__int64 x1, y1, p;
	if (b == 0)
	{
		*x = 1;
		*y = 0;
		return a;
	}

	p = e_gcd(b, a % b, &x1, &y1);

	*x = y1;
	*y = x1 - (a / b) * y1;
	return p;
}

__int64 abs(__int64 a)
{
	return (a > 0) ? a : -a;
}

int main()
{
	__int64 x, y, m, n, L;
	__int64 a, b, t, r, gcdans, lcmans, ans;

	while (scanf("%I64d %I64d %I64d %I64d %I64d", &x, &y, &m, &n, &L) != -1)
	{
		x %= L;
		y %= L;
		m %= L;
		n %= L;

		if (m > n)
		{
			a = m - n;
			b = ((y - x) % L + L) % L;
		}
		else
		{
			b = ((x - y) % L + L) % L;
			a = n - m;
		}
		
		gcdans = e_gcd(a, L, &t, &r);
		lcmans = a / gcdans * L;
		if (b % gcdans != 0)
		{
			printf("Impossible\n");
		}
		else
		{
			b /= gcdans;
			L /= gcdans;
			ans = ((b * t) % L + L) % L;
			printf("%I64d\n", ans);
		}
	}
	return 0;
}