TopCoder SRM 620 Div1 Easy PairGame

ここまで9回連続Easyを正解できていたのに、Easy/Medium落としたうえChallengeミスしてひどいことに。
http://community.topcoder.com/stat?c=problem_statement&pm=13142

問題

自然数の対(x,y)に対し、処理を1回行うと(x+y,y)または(x,x+y)に遷移できる。
ここで、(a,b)と(c,d)2つの対があるとする。
処理を繰り返してこれら両方に遷移可能な対(x,y)のうち、x+yが最大なものを答えよ。

解法

一見遷移は毎回2通りあるが、逆向きを考えると1つしか有効なものはない。
例えば(p,q)はp<qなら(p,q-p)から、p>qなら(p-q,q)から遷移してこない。

よって、(a,b)と(c,d)両方から逆方向に遷移を繰り返し、一致するものを探せばよい。
なお、再帰関数で行うとスタックがあふれるので注意。
a=1000000, b=1とかだと10^6回再帰する。
自分はそれでやらかした。

class PairGame {
	public:
	int maxSum(int a, int b, int c, int d) {
		set<pair<int,int> > S[2];
		S[0].clear();
		S[1].clear();
		
		while(a>0 && b>0) {
			S[0].insert(make_pair(a,b));
			if(a<=b) b-=a;
			else a-=b;
		}
		while(c>0 && d>0) {
			S[1].insert(make_pair(c,d));
			if(c<=d) d-=c;
			else c-=d;
		}
		
		int ma=-1;
		ITR(it,S[0]) {
			if(S[1].find(*it)!=S[1].end()) ma=max(ma,it->first+it->second);
		}
		return ma;
	}
};

まとめ

再帰は10^4位に押さえとかないとダメだな…。
こんなしょうもないミスはもったいない。