TopCoder SRM 620, Division 2, level 2 : PairGameEasy

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=13161&rd=15853

問題概要

　正整数の順序対 ( x, y ) について、( x + y , y ) または ( x, y + x ) に変化させる操作を任意回数できる。
　正整数 a, b, c, d が与えられる。( a, b ) から ( c, d ) を作れるか否か、求めよ。

解法

　a, b, c, d の最大値を M と書きます。
　Division 1, Level 1 での考察と同様に、ある順序対 ( x, y ) が操作によって作られたとすれば、直前の状態として有り得るのは ( x - y, y ) か ( x, y - x ) です。しかし、正整数のみについて考えているので、x - y や y - x が 0 以下になるケースは除外できます。この内一方は必ず 0 以下なので、結局、( x, y ) の直前の順序対は一意に定まります。従って、最終状態である ( c, d ) から逆順にシミュレートをすることで、( c, d ) を生成できる全ての順序対を で計算することができます。問題の答えは、min( c, d ) < 0 となる前に ( a, b ) に一致する ( c', d' ) が現れるか否かと一致します。

コード

class PairGameEasy
{
public:
	string able( int a, int b, int c, int d )
	{
		while ( 0 < min( c, d ) )
		{
			if ( a == c && b == d )
			{
				return "Able to generate";
			}

			if ( c < d )
			{
				d -= c;
			}
			else
			{
				c -= d;
			}
		}
		return "Not able to generate";
	}
};