TopCoder SRM 661 Div1 Easy: MissingLCM（素因数分解）

解法

ならばが成り立つ。

が成り立つ時、Mを除いて、が成り立つのはどういう時かを考える。Mのある約数Pについて、Pの倍数がの中に含まれているにもかかわらず、の中にPの倍数が含まれていなかった場合、はPの倍数になるが、はPの倍数にならない場合があり、その場合は等号が成り立たない。そのような時はMを取り除くことはできない。逆に、Mの約数のうちに含まれるものが全てにも含まれている場合は、が成り立つ。

このようにして、Mを2Nから1ずつ減らしていき、減らせなくなったら返せば良い。

コード

public class MissingLCM {
	private final int MAX = 2000001;

	public int getMin(int N) {
		// divisor[i]:= iの約数となる最小の素数
		int[] divisor = new int[MAX];
		for (int i = 1; i < MAX; i++) {
			divisor[i] = i;
		}
		for (int i = 2; i < MAX; i++) {
			if (divisor[i] == i) {
				for (int j = i * 2; j < MAX; j += i) {
					divisor[j] = Math.min(divisor[j], i);
				}
			}
		}

		int M = 2 * N;
		while (M > N + 1) {
			int v = M;
			while (v != 1) {
				int div = divisor[v];
				int cur = 1;
				while (v % div == 0) {
					v /= div;
					cur *= div;
					if ((cur <= N && (M - 1) - N >= cur) || cur > N) {
						// セーフ
						continue;
					}
					return M;
				}
			}
			M--;
		}

		return M;
	}

}