首页 > 代码库 > POJ1061 青蛙的约会 (扩展欧几里德)

POJ1061 青蛙的约会 (扩展欧几里德)

本文出自:http://blog.csdn.net/svitter


题意:青蛙绕圈跳, 初始位置X,Y,速度M,N,方向相反,L为模。最后能否相遇?相遇时间是什么?


本题目为扩展欧几里德,扩展欧几里德介绍:

关于扩展欧几里德方程

ax + by = c(1)

可以用来求是否有解。即是否存在c满足这个方程。

exgcd(a, b, x, y)是用来求ax + by = gcd(a, b)中x的值和y的值的。如果仅仅只是判断(1)是否有解,直接看gcd(a, b)能否整除c即可。

然后开始分析本题:

设最后在坐标s相遇,A转了b圈,B转了b`圈,花费时间为a,那么可以得到两个方程:

Ma + X = Lb + s;(3)

Na + Y = Lb` + s;(4)

如果s有解,那么方程 (M - N)a+L(b - b`) = Y - X有解。(即(3) - (4))

以此判断impossible的情况;(一开始做的时候没弄懂题意,以为不同方向,shit- -)

解出的a可能不是一个正数,或者比最小数大。

通解为

x1 = x + L / gcd(m-n, L) * t;t为任意整数;

y1 = y - L / gcd(m-n,L) * t;

证明:

已知ax  + by  = c

ax1 = x * a + lcm(a, b) * t;

by1 = y * b - lcm(a, b)*t;

所以ax1 + by1 = c;


代码如下:

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

#define lln long long int

lln gcd(lln a, lln b)
{
    if(b == 0)
        return a;
    return gcd(b, a % b);
}

lln exgcd(lln a, lln b, lln &x, lln &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y);
    int t = x;
    x = y;
    y = t - (a / b) * y;
    return d;
}

void ace()
{
    lln X, Y, M, N, L;
    lln dis;
    lln a, b, x, y, c, gc, d;
    while(scanf("%lld %lld %lld %lld %lld", &X, &Y, &M, &N, &L) == 5)
    {
        a = M - N;
        c = exgcd(a, L, x, y);

        dis = Y - X;
        if(dis % c != 0)
        {
            printf("Impossible\n");
            continue;
        }
        x = x * (dis / c);
        y = y * (dis / c);

        gc = L / c;
        gc = gc > 0? gc : -gc;

        while(x > 0)
        {
            x -= gc;
        }
        while(x < 0)
        {
            x += gc;
        }

        printf("%lld\n", x);
    }
}

int main()
{
    ace();
    return 0;
}


POJ1061 青蛙的约会 (扩展欧几里德)