TopCoder SRM 611, Division 1, Level 1 : LCMSet

問題文

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

問題概要

　整数集合について、set LCM を、その集合の冪集合のそれぞれの要素から得られる LCM の集合とする。
　二つの整数集合 A, B が与えられる。二つの集合の set LCM が一致するかどうかを求めよ。

解法

　二つの集合が互いに（ ( S, T ) = ( A, B ) と ( S, T ) = ( B, A ) の両方で）以下の condition を満たせば全体で valid になります。

• T の任意の要素を S から作れる

初期の要素を作れない場合は自明にダメです。不足が無いという点については後で述べるとして、ある一つの T の x を他方の集合 S から作れるかどうかの判定について述べます。これは Division 2, Level 2 と同じ内容になります。

S からある値 x を作れるかの判定

　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 と一致すれば S から x を作ることができます。

全体の方針の妥当性

　この集合の考え方を用いて、全体の方針の妥当性についても考えることができます。元の集合に含まれないような set LCM の要素であっても、それを生成した値を生成するそれぞれの集合から生成できます*1。集合で考えたときに Bitwise OR のような性質をもつということを踏まえると分かりやすいと思います。

コード

typedef long long LL;
typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )

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

class LCMSet
{
public:
	string equal( vector <int> A, vector <int> B )
	{
		return solve( A, B ) && solve( B, A ) ? "Equal" : "Not equal";
	}

	bool solve( const VI &A, const VI &B )
	{
		FOR( x, A )
		{
			LL l = 1;
			FOR( b, B )
			{
				if ( !( x % b ) )
				{
					l = lcm( l, b );
				}
			}
			if ( l != x )
			{
				return false;
			}
		}

		return true;
	}
};

*1:分かりづらい文ですみません＞＜