学步园

拓展欧几里得解线性方程组

#include "iostream"
#include "cstdio"
using namespace std;
long long d;

long long GcdFull(long long a,long long b,long long &x,long long &y)
{
	if (b == 0){
		x = 1;
		y = 0;
		return a;
	}
	long long g = GcdFull(b,a % b,x,y);
	long long t = x;
	x = y;
	y = t - (a / b) * y;
	return g;
}

int main(void)
{
	long long a,b,x,y,l,m,n,gcd;
	long long s1,s2;
	while(cin >> x >> y >> m >> n >> l)
	{
		a = n - m;
		b = l;
		d = x - y;
		if ( d % (gcd = GcdFull(a,b,s1,s2)))
		{
			printf("Impossible\n");
		}
		else
		{
			b /= gcd;
			d /= gcd;
			s1 = ((s1 * d ) % b + b) % b;
			printf("%lld\n",s1);
		}
	}
	return 0;
}