SRM611 Div1 Easy "LCMSet"

問題

TopCoder Statistics - Problem Statement

訳

空でない正の整数のシーケンス s1, s2, ..., sK の最小公倍数は、シーケンスのそれぞれの数で割り切れることのできる、最小の整数である。最小公倍数を返す関数を"lcm"と定義する。例えば、lcm(3) = 3, lcm(4, 6) = 12, そしてlcm(2, 5, 7) = 70である。

与えられたシーケンスをSとしたとき、LCM(S)を次のように定義する。LCM(S) = Sの任意のサブシーケンスの最小公倍数のセット。例えば、S={2, 3, 4}であれば、LCM(S) = {2, 3, 4, 6, 12}となる。

あなたはint[] A, Bが与えられる。LCM(A) = LCM(B)であるかどうかを返せ。

制約

1 <= A, Bの要素数 <= 50
2 <= A[i], B[i] <= 10^9

考えたこと

Aの１つ要素に着目したとき、それがBのサブシーケンスの最小公倍数であるかを調べる。反対に、Bの１つ要素に着目したとき、それがAのサブシーケンスの最小公倍数であるかを調べる。

Div2の簡単版の考えを、それぞれの要素に適用してやればいける。

ソースコード

class LCMSet {
public:
    
    string equal(vector <int> A, vector <int> B) {
        // Aの要素に着目
        for (int i = 0; i < A.size(); i++ ) {
        	int x = A[i];
        	int a = 1;
        	for( int j = 0; j < B.size(); j++ ) {
            	if( x % B[j] == 0 ) a = lcm(a, B[j]);
            }
            if( a != x ) return "Not equal";
        }
        
        // Bの要素に着目
        for (int i = 0; i < B.size(); i++ ) {
        	int x = B[i];
        	int a = 1;
        	for( int j = 0; j < A.size(); j++ ) {
            	if( x % A[j] == 0 ) a = lcm(a, A[j]);
            }
            if( a != x ) return "Not equal";
        }
        
        return "Equal";
    }
    
    // A, Bの最小公倍数を返す
    int lcm(long long A, long long B) {
        return A * B / gcd(A, B);
    }
    
    // A, Bの最大公約数を返す
    int gcd(long long A, long long B){
        if (A < B) swap(A, B);
        if (A % B == 0) return B;
        return gcd(B, A % B);
    }
};