eea.cpp (uva 718)

#include <assert.h>

#include <stdio.h>

#include <algorithm>

#include <iostream>

using namespace std;

#define long long long

const int oo = 0x3c3c3c3c;

const long oooo = 1LL * oo * oo;

#define N 1003

int L, n, A, B;

int a[N], b[N];

bool c[N][N];

void eea(long a, long b, long &x, long &y) {  // a,b >= 0

    if (b == 0) {

        x = 1, y = 0;

        return;

    }

    long q = a / b, r = a % b, s, t;

    eea(b, r, s, t);

    x = t, y = s - q * t;

}

long f(long a1, long b1, long a2, long b2) {  // a1*x+b1==a2*y+b2==min

    long x, y, c = b2 - b1, GCD = __gcd(a1, a2);

    if (c % GCD) return oooo;

    eea(a1, a2, x, y);

    assert(a1 * x + a2 * y == GCD);

    x = x * (c / GCD);

    y = -y * (c / GCD);

    assert(abs(a1 * x - a2 * y) == abs(b2 - b1));

    while (x < 0 || y < 0) x += a2 / GCD, y += a1 / GCD;

    while (x >= a2 / GCD && y >= a1 / GCD) x -= a2 / GCD, y -= a1 / GCD;

    // printf("f(%lld, %lld, %lld, %lld) = %lld\n", a1, b1, a2, b2, a1*x+b1);

    assert(a1 * x + b1 == a2 * y + b2);

    return a1 * x + b1;

}

int main() {

    int t;

    scanf("%d", &t);

    while (t--) {

        scanf("%d%d%d%d", &L, &n, &A, &B);

        for (int i = 1; i <= n; ++i)

            scanf("%d%d", &a[i], &b[i]);

        for (int i = 1; i <= n; ++i)

            for (int j = 1; j <= n; ++j)

                c[i][j] = f(a[i], b[i], a[j], b[j]) < L;

        for (int k = 1; k <= n; ++k)

            for (int i = 1; i <= n; ++i)

                for (int j = 1; j <= n; ++j)

                    c[i][j] |= c[i][k] && c[k][j];

        bool ok = A == B;

        for (int i = 1; i <= n; ++i)

            if (!ok)

                for (int j = 1; j <= n; ++j)

                    if (c[i][j] && (A - b[i]) % a[i] == 0 && (B - b[j]) % a[j] == 0)

                        ok |= A >= b[i] && B >= b[j];

        if (ok)

            cout << "It is possible to move the furniture." << endl;

        else

            cout << "The furniture cannot be moved." << endl;

    }

}

Code này đã được dùng để nộp cho một bài trên UVa.