TopCoder SRM 611, Division 2, Level 1 : LCMSetEasy

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=13040&rd=15844

問題概要

　正整数の集合 S が与えられる。S の部分集合であって、その LCM が x となるものが存在するかどうか求めよ。

解法

　S の要素数を N と表記します。
　LCM の単位元は 1 なので、1 を LCM の初期値としてもちつつ S を走査します。S の各要素 s について、s との LCM で値を更新するべきかを適当に判定できれば、 で解くことができます。
　x と等しい LCM を構成するときに必要となる可能性がある要素は、その定義から x を割り切る値です。実は、s が x を割り切るならば、それだけで LCM を更新してしまってよいです。というのは、この条件下では使ってはならない要素が存在しないからです。素因数のレベルで考えると分かりやすくなります。x の素因数分解によって得られる（多重）集合を考えると、x を割り切る値の素因数分解によって得られる集合の上位集合となっています。途中の段階で求まっている LCM を a として、a を lcm( a, s ) で更新するとします。このとき、LCM は a * s / gcd( a, s ) で計算されます。先程の集合で考えると、既に集合に加えられた要素の集合は gcd( a, s ) から（同様に素因数分解で）得られる集合と一致します。従って、一度も加えられていない要素だけが集合に加えられることになり、余計な値で更新してしまうことは無いと分かります。LCM の構成に必要となる可能性がある要素全てに対して処理をすることを考えているので、余剰が無いことによって方針は妥当ということになります。
　こうして求まった LCM が、x と一致すれば valid です。
　

コード

typedef long long LL;

#define FOR( v, c ) for ( auto &v : c )

LL lcm( LL a, LL b )
{
	return a / __gcd( a, b ) * b;
}

class LCMSetEasy
{
public:
	string include( vector <int> S, int x )
	{
		LL l = 1;
		FOR( s, S )
		{
			if ( !( x % s ) )
			{
				l = lcm( l, s );
			}
		}
		
		return l == x ? "Possible" : "Impossible";
	}
};