青蛙的约会---poj1061（扩展欧几里德）

题目链接：http://poj.org/problem?id=1061

就是找到满足 (X+mt)-(Y+nt) = Lk 的 t 和 k 即可

上式可化简为 (n-m)t + Lk = X-Y;满足ax+by=c的形式 所以我们可以用扩展欧几里德求t和k;

 

 由于上式有解当且仅当 c % gcd(a, b) = 0;

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <string>

#include <vector>

#include <algorithm>

#include <map>

#include <queue>

#include <stack>

#include <math.h>

using namespace std;

#define met(a, b) memset(a, b, sizeof(a))

#define N 10053

#define INF 0x3f3f3f3f

const int MOD = 1e9+;

typedef long long LL;

LL gcd(LL a, LL b)

{

    return b ==  ? a : gcd(b, a%b);

}

void ex_gcd(LL a, LL b, LL &x, LL &y)

{

    if(b == )

    {

        x = ;

        y = ;

        return ;

    }

    ex_gcd(b, a%b, x, y);

    LL t = x;

    x = y;

    y = t - a/b*y;

}

int main()

{

    LL X, Y, L, n, m;

    while(scanf("%lld %lld %lld %lld %lld", &X, &Y, &m, &n, &L) != EOF)

    {

        LL a, b, x, y, c;

        a = n-m, b = L, c = X-Y;

        LL r = gcd(a, b);

        if(c%r)

        {

            puts("Impossible");

            continue;

        }

        a = a/r;

        b = b/r;

        c = c/r;

        ///之所以让他们都除以r是为了让ab互质，然后结果就相当于是x和y的c倍；

        ex_gcd(a, b, x, y);///此时的a和b互质，求得就是ax+by=1;的解最终的解要*c;

        x = x*c;

        x = x % b;///要求的是最小的解，所以要对b求余；

        while(x <= )

        {

            x += b;

        }

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

    }

    return ;

}