WARush

SRMの結果とか、解けた問題のコードを書いていきます

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);
    }
};