POJ 1061 青蛙的约会（扩展欧几里得）

　　根据题意，两个青蛙跳到同一个点上才算是遇到了，所以有 (x+m*t) - (y+n*t) = p * ll;  (t是跳的次数，ll是a青蛙跳的圈数跟b青蛙的圈数之差。整个就是路程差等于纬度线周长的整数倍)，转化一下： (n-m) * t + ll * p = x – y；令 a = n-m,  b = ll,  c = gcd(a, b),  d = x-y；有 a * t + b * p = d；之后根据exgcd就可以求出来了，但这是答案吗？显然不是，因为题让我们求最小的解，而刚才求出的是通解，所以还需要了解一个知识：

设我们求出的通解是x，y；式子是 ax+by=c； k是一个随机整数；gcd是gcd(a,b)；则有公式

x = x0 + (b/gcd)*k 

y = y0 - (a/gcd)*k

在本题我们要求x0，我们已知的是x，所以对(b/gcd)取模，判断是否小于0，如果是就+=(b/gcd)

 

#include <cstdio>
#include <iostream>
using namespace std;

const int INF=0x3f3f3f3f;
typedef long long ll;
#define PI(A) printf("%d
",A)
#define SI(N) scanf("%d",&(N))
#define SII(N,M) scanf("%d%d",&(N),&(M))
#define cle(a,val) memset(a,(val),sizeof(a))
#define rep(i,b) for(int i=0;i<(b);i++)
#define Rep(i,a,b) for(int i=(a);i<=(b);i++)
#define reRep(i,a,b) for(int i=(a);i>=(b);i--)
const double EPS= 1e-9 ;

/*  /////////////////////////     C o d i n g  S p a c e     /////////////////////////  */

const int MAXN= 1000 + 5 ;


ll x,y,m,n,L;

//exgcd模板
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    ll d=a;
    if (b!=0){
        d=exgcd(b,a%b,y,x);
        y-=(a/b)*x;
    }else{
        x=1;y=0;
    }
    return d;
}


int main()
{
    cin>>x>>y>>m>>n>>L;

    ll a=n-m,b=L,c,d=x-y;
    ll e,f;
    c=exgcd(a,b,e,f);
    if (d%c!=0)
    {
        puts("Impossible");
    }else{
        e=e*(d/c);
        //e对(b/gcd)取模
        e%=b/c;
        //判断是否小于0，如果是就+=(b/gcd)
        if (e<0) e+=b/c;
        cout<<e<<endl;
    }

    return 0;
}