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の1つ要素に着目したとき、それがBのサブシーケンスの最小公倍数であるかを調べる。反対に、Bの1つ要素に着目したとき、それが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); } };