Codeforces #139 Unsolvable

問題概要

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

方針

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

ソースコード

view plainprint?

1. const long long MOD = 1000000007LL;  
2. int mers[] = {  
3.     2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607,  
4.     1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941,  
5.     11213, 19937, 21701, 23209, 44497, 86243,   
6.     110503, 132049, 216091, 756839, 859433,  
7.     1257787, 1398269, 2976221, 3021377, 6972593,  
8.     13466917, 20996011, 24036583  
9. };  
10.   
11. int main() {  
12.     int n;  
13.   
14.     cin >> n;  
15.     int x = mers[n-1];  
16.     long long ret = 1;  
17.   
18.     REP(i, x-1) {  
19.         ret <<= 1;  
20.         ret %= MOD;  
21.     }  
22.   
23.     cout << (ret+MOD-1)%MOD << endl;  
24.       
25.     return 0;  
26. }  

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で割れることが一目瞭然なので、素数じゃないのは明らかか。。