TopCoder SRM611: LCMSetEasy

x が y で割り切れない場合は、y には x より余分な素因数が含むので、最小公倍数に含めてはいけない。
それ以外の場合は、最小公倍数で取り込むデメリットはないので、全て取り込んだ上で x と同じになるかどうかを判定すればよい。

public class LCMSetEasy {
    static public long Gcd(long s, long t) {
        return t != 0 ? Gcd(t, s % t) : s;
    }

    static public long Lcm(long s, long t) {
        return s / Gcd(s, t) * t;
    }

    public string include(int[] S, int x) {
        long lcm = 1;

        foreach (var s in S) {
            if (x % s == 0)
                lcm = Lcm(lcm, s);
        }

        return lcm == x ? "Possible" : "Impossible";
    }
}