SRM 652 div1 easy: ThePermutationGame

div2 medで簡単なバージョンの問題を解いていたので、かなり簡単に感じた。

問題:http://community.topcoder.com/stat?c=problem_statement&pm=13229&rd=16316

解法:結論から言うと、Bob側は1〜Nまでの任意の周期の順列を用意できるので、アリスがf(x) = 1と必ずなるようにするためには、xは1〜Nの最小公倍数の倍数でなければならない。
これがわかれば後は簡単で、それぞれの素因数について、一番乗数が多いものを選んできて、掛け算すれば良い(例えばN=100だったら2の素因数として一番乗数が大きいのは64 = 2^6)
あとは証明。鳩の巣論法によってBobはNより大きい周期を作ることができない。また、BobはN以下の任意の周期を作り出すことができる。例えば、[K, 1, 2, ... K-1, (あと適当)]とすれば周期Kの順列を作り出せる。

以下ソースコード

const int MAX = 100100;
const ll MOD = 1000000007;
bool isPrime[MAX];

void init() {
    for (int i = 0; i < MAX; i++) isPrime[i] = true;
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i < MAX; i++) {
        if (isPrime[i]) {
            for (int j = 2; j * i < MAX; j++) {
                isPrime[i*j] = false;
            }
        }
    }
}

class ThePermutationGame {
public:
    int findMin(int N) {
        init();
        ll ret = 1;
        for (int i = 2; i < MAX; i++) {
            if (i > N) break;
            if (isPrime[i]) {
                ll now = 1;
                while (now <= N) {
                    now *= i;
                }
                now /= i;
                ret *= now;
                ret %= MOD;
            }
        }
        return (int)ret;
    }
};