SRM652 Div1E: ThePermutationGame

問題

ボブが1からNまでの自然数を並び替えて数列pを作る（ここではpは1-indexedとしておく）。アリスはf(1)=p[1]、f(m)=p[f(m-1)]となるようにfを考える。ボブがどのように数列pを作ってもf(x)=1となるような最小のxを求めよ。

解法

ボブがどんな数列を作ってもf(q)=1となるqが存在し、f(q+1)=p[f(q)]=p[1]=f(1)となるので、fは必ず周期がある数列になる。この周期の最小公倍数が求めるxとなる。周期はN以下の自然数全てについて考えられるので、要するにN以下の自然数全ての最小公倍数を求めればいい。

コード

import java.util.ArrayList;

public class ThePermutationGame {

	public int findMin(int N) {
		int INF = 1000000007;

		ArrayList<Integer> list = new ArrayList<>();
		list.add(2);
		for (int i = 1; 2 * i + 1 <= N; i++) {
			int n = 2 * i + 1;
			boolean prime = true;
			for (Integer integer : list) {
				if (n % integer == 0) {
					prime = false;
					break;
				}
			}
			if (prime) {
				list.add(n);
			}
		}

		long ans = 1;
		for (Integer num : list) {
			long p = num;
			while (p <= N) {
				p *= num;
			}
			p /= num;
			ans *= p;
			ans %= INF;
		}

		return (int) ans;
	}
}