青蛙的约会 POJ - 1061 扩展欧几里得解二元一次不定方程

#include <iostream>
#define ll long long
using namespace std;
ll exgcd(ll a,ll b,ll &x,ll &y) {
	if(!b) {//解方程求 x,y a*x+b*y = gcd(a,b)
		x=1,y=0;
		return a;
	}
	ll re=exgcd(b,a%b,x,y),tmp=x;
	x=y,y=tmp-(a/b)*y;
	return re;
}
int main() {
	ll x,a,b,y,c,m,n,l,p;
	cin>>x>>y>>m>>n>>l;
	a = n-m;
	b = l;
	c = x-y;
	//求 ax + by = c
	p = exgcd(a,b,x,y);// 先求 ax + by = gcd(a,b)
	if(c%p!=0) {// 无解 
		printf("Impossible\n");
	} else {
		x = x*c/p; // 这里输出 x, 解*c/p 为通解
		if(x>=0) { //求最小解
			x%=b/p;
		} else {
			x = x%b/p + b/p;
		}
		printf("%lld\n",x);
	}

	return 0;
}