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

就是找到满足 (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+7;

typedef long long LL;

LL gcd(LL a, LL b)
{
    return b == 0 ? a : gcd(b, a%b);
}

void ex_gcd(LL a, LL b, LL &x, LL &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        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 <= 0)
        {
            x += b;
        }
        printf("%lld
", x);
    }
    return 0;
}

View Code

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

相关推荐