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\n",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- ;

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

const int MAXN=  +  ;

ll x,y,m,n,L;

//exgcd模板

ll exgcd(ll a,ll b,ll &x,ll &y)

{

    ll d=a;

    if (b!=){

        d=exgcd(b,a%b,y,x);

        y-=(a/b)*x;

    }else{

        x=;y=;

    }

    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!=)

    {

        puts("Impossible");

    }else{

        e=e*(d/c);

        //e对(b/gcd)取模

        e%=b/c;

        //判断是否小于0，如果是就+=(b/gcd)

        if (e<) e+=b/c;

        cout<<e<<endl;

    }

    return ;

}

巴特西

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

最新文章

热门文章