SRM620 Div1 Easy "PairGame"

問題

TopCoder Statistics - Problem Statement

訳

この問題では、正の整数のペアについて考える。ペアが与えられたとき、あなたはそこに任意の回数だけ操作を行える。１回の操作で、あなたは片方の数値に、もう片方の数値を足して、新たなペアに変化させることが出来る。もし現在のペアが(x, y)だとすると、次のペアは(x+y, y)もしくは(x, x+y)とすることができる。

例えば、(1, 2)が最初のペアだとすると、(3, 2)に変化させることができ、それを(3, 5)、さらに(3, 8)と変化させることが出来る。

あなたは４つのint a, b, c, dが与えられる。以下のような(x, y)を見つけよ。

(x, y)から始めて(a, b)へと変化させることが出来る。
同じく(x, y)から始めて(c, d)へと変化させることが出来る。

(a, b)へと変化させるための操作回数と(c, d)へと変化させるための操作回数は違っていても構わない。

そのような(x, y)が１つでもあるのなら、その中でx+yが最も大きいものを選び、その値を返せ。

制約

1 <= a, b, c, d <= 10^6

考えたこと

やばい全然分からん・・

～３０分後～

逆から考えると実は１パターンしかないやーん！！
x < yの場合
(x, y) -> (x, y-x)
x > yの場合
(x, y) -> (x-y, y)

ぐぬぬ・・

ソースコード

vector<pair<int, int>> v;

class PairGame {

    public:

    int maxSum(int a, int b, int c, int d) {
        while (a > 0 && b > 0) {
            v.push_back(make_pair(a, b));
            if (a < b) {
                b -= a;
            }
            else{
                a -= b;
            }
        }

        sort(v.begin(), v.end());
        
        while (c > 0 && d > 0) {
            if (binary_search(v.begin(), v.end(), make_pair(c, d))) {
                return c + d;
            }
            if (c < d) {
                d -= c;
            }
            else{
                c -= d;
            }
        }

        return -1;
    }
};