POJ1061 青蛙的约会(拓展欧几里得)

19/08/09 更新注意一下如果a的值小于0的话需要两边同时乘以-1这样保证两边都是正数顺便更新一下代码

#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
void gcd(ll a,ll b,ll& x,ll& y,ll& d)
{
	if(!b)
	x=1,y=0,d=a;
	else
	gcd(b,a%b,y,x,d),y-=a/b*x;
}
int main()
{
	ll x,y,n,m,l;
	while(~scanf("%lld%lld%lld%lld%lld",&x,&y,&n,&m,&l))
	{
		ll a=m-n;
		ll b=l;
		ll c=(x-y);
		ll xx,yy,d;
		if(a<0)
		{
			a=-a;
			c=-c;
		}
		gcd(a,b,xx,yy,d);
		if(c%d)
		printf("Impossible\n");
		else
		{
			xx*=c/d;
			b/=d;
			printf("%lld\n",(xx%b+b)%b);
		}
	}
}