[poj] 1061 青蛙的约会

[原题

显然我们要求得是(s+pxequivt+qx(mod L))是否成立
等式等价于(p-q)x+Ly=t-s
所以求ex_gcd的最小整数解即可

#include<cstdio>
#include<algorithm>
typedef long long ll;
using namespace std;
ll x,y,m,n,l,ans,k,t,gg,a,b,c;

ll gcd(ll x,ll y)
{
    return !y?x:gcd(y,x%y);
}

void ex_gcd(ll a,ll b,ll &x,ll &y)
{
    if (!b)
    {
	x=1;
	y=0;
	return ;
    }
    ex_gcd(b,a%b,y,x);
    y-=a/b*x;
}

int main()
{
    scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l);
    a=((m-n)%l+l)%l;
    b=l;
    c=((y-x)%l+l)%l;
    gg=gcd(a,b);
    if (c%gg)
    {
	printf("Impossible");
	return 0;
    }
    a/=gg;
    b/=gg;
    c/=gg;
    ex_gcd(a,b,t,k);
    t=(t%b+b)%b;
    t*=c;
    printf("%lld
",t%b);
    return 0;
}