SRM611 Div2 Medium "LCMSetEasy"
問題
TopCoder Statistics - Problem Statement
訳
空でない正の整数のシーケンス s1, s2, ..., sK の最小公倍数は、シーケンスのそれぞれの数で割り切れることのできる、最小の整数である。最小公倍数を返す関数を"lcm"と定義する。例えば、lcm(3) = 3, lcm(4, 6) = 12, そしてlcm(2, 5, 7) = 70である。
あなたはint[] Sと、int xが与えられる。Sの任意のサブシーケンスのうち、最小公倍数がxとなるものを探し出したい。正確には、Sのサブシーケンスを s1, s2, ..., sK としたとき、x = (s1, s2,..., sK)となるものを探したい。もし見つかるようであれば"Possible"を、そうでなければ"Impossible"を返せ。
制約
1 <= Sの要素数 <= 50
1 <= S[i] <= 10^9
Sの整数は、それぞれ互いに異なるものである。
2 <= x <= 10^9
解法
2値の最小公倍数は簡単に出せる。
lcm(A, B) = A * B / gcd(A, B)
それを利用すると3値、4値の最小公倍数も簡単に出すことができる。
lcm(A, B, C) = lcm(lcm(A, B), C) lcm(A, B, C, D) = lcm(lcm(lcm(A, B), C), D)
初期の最小公倍数をaとする。シーケンスの各要素iについて、xで割り切れるものであれば、a = lcm(a, i)とする。最終的にa == xであればok。
xで割り切れないものを対象としない理由は、aがxを超過しないようにしているのと、xにない余計な素因数を紛れ込ませないため。最終的にa < xになったばあいは、xは単なる公倍数だったということ。
なぜこれでいいかは、下記を見るとなんとな~く分かるかもしれない。
★lcm(3) = 3 3 = 3^1 3 = 3^1 ★lcm(4, 6) = 12 4 = 2^2 6 = 2^1 * 3^1 12= 2^2 * 3^1 ★lcm(2, 5, 7) = 70 2 = 2^1 5 = 5^1 7 = 7^1 70= 2^1 * 5^1 * 7^1 ★lcm(8, 9, 12) = 72 8 = 2^3 9 = 3^2 12= 2^2 * 3^1 72= 2^3 * 3^2
ソースコード
class LCMSetEasy { public: string include(vector <int> S, int x) { int a = 1; for (int i = 0; i < S.size(); i++ ){ if( x % S[i] == 0 ) a = lcm(a, S[i]); } return a == x ? "Possible" : "Impossible"; } // 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); } };