SRM 537 DIV1 275 KingXNewCurrency

問題

　正の整数A, B, Xが与えられる。任意の非負正数p, qに対してAp + Bq = Xp' + Yq'となるような非負正数p', q'が存在するような正の整数Yの個数を求めよ。

方針

　あるYにおいて、任意の非負整数p, qに対して問題の等式が成り立つような(p', q')が存在するとする。このとき特に(p, q) = (1, 0)とすると、A = Xp' + Yq'が成り立つ。同様に、(p, q) = (0, 1)のときは、B = Xp' + Yq'が成り立つ。つまり、AとBは、X, Yの非負線形結合で表すことができる。

　逆に、AとBの両方がX, Yの非負線形結合で表されるとする。このとき、明らかに任意のp, qに対して問題の等式を満たすp', q'が存在する。

　よって、問題の等式を満たすYの個数は、A, BをX, Yの非負線形結合で表すことのできるようなYの個数と同じ。

ソースコード

　O(N²)バージョンと、拡張ユークリッド互除法を用いたO(N (log(N))²)バージョンを載せて起きます。今回の問題では、O(N²)で十分です。

class KingXNewCurrency {
public:
    int howMany(int A, int B, int X) {
        if (A % X == 0 && B % X == 0)
            return -1;

        int ret = 0;
        for (int Y = 1; Y <= 200; Y++) {
            bool cana = false;
            bool canb = false;

            for (int t = A; t >= 0; t -= X)
                if (t % Y == 0)
                    cana = true;

            for (int t = B; t >= 0; t -= X)
                if (t % Y == 0)
                    canb = true;

            if (cana && canb)
                ++ret;
        }

        return ret;
    }
};

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

class KingXNewCurrency {
    bool canMake(int A, int x, int y, int g, int p, int q) {
        int lcm = x * y / g;
        int dp = lcm / x;
        int dq = lcm / y;
        p = A * p / g;
        q = A * q / g;

        if (p < 0) {
            int add = (-p + dp - 1) / dp;
            p += add * dp;
            q -= add * dq;
        }
        else if (q < 0) {
            int add = (-q + dq - 1) / dq;
            p -= add * dp;
            q += add * dq;
        }

        return p >= 0 && q >= 0;
    }

public:
    int howMany(int A, int B, int X) {
        if (A % X == 0 && B % X == 0)
            return -1;

        int p, q, g, ret = 0;
        bool cana, canb;
        for (int Y = 1; Y <= 200; Y++) {
            g = extGcd(X, Y, p, q);

            cana = (A % g) ? false : canMake(A, X, Y, g, p, q);
            canb = (B % g) ? false : canMake(B, X, Y, g, p, q);
            if (cana && canb)
                ++ret;
        }

        return ret;
    }
};