Codeforces #139 Unsolvable

問題概要

z = [x/2] + y + xy, z > 0
を満たす正の整数x, yが存在しないようなzのうち、n番目に小さなものをMOD 1000000007で答えよ。ただし、[a]はaの整数部を表す。

方針

こういう数論系の問題は好きです。Editorialのように式変形していくと、メルセンヌ素数と関連する値になることがわかります。

ソースコード

const long long MOD = 1000000007LL;
int mers[] = {
    2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607,
    1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941,
    11213, 19937, 21701, 23209, 44497, 86243, 
    110503, 132049, 216091, 756839, 859433,
    1257787, 1398269, 2976221, 3021377, 6972593,
    13466917, 20996011, 24036583
};

int main() {
    int n;

    cin >> n;
    int x = mers[n-1];
    long long ret = 1;

    REP(i, x-1) {
        ret <<= 1;
        ret %= MOD;
    }

    cout << (ret+MOD-1)%MOD << endl;
    
    return 0;
}

おまけ

2^p - 1が素数となるためには、pは素数でなくてはいけません。1023とかパッと見、素数っぽいですが、2^10 - 1で10は素数ではないため、1023は素数ではありません。
いや、、こんなことしなくても、1023は3で割れることが一目瞭然なので、素数じゃないのは明らかか。。