【题解】Unsolvable 数论 CF139E ——quhengyi11

qwq

机房快关门了突然想起来上午做的这题还算有点新颖所以记录一下吧

题意

求 $\mathbf{S}=N^* – \{z|z=[ \frac{x}{2}]+y+xy,x,y\in N^*\}$的前 $40$个元素

题解

看着这个数据范围和样例我就猜了好几个结论，不过没有一个猜中的= =

首先令 $x=2k,2k+1$

$$z=k+y+2ky$$
$$z=k+2y+2ky$$

这步我也想到了不过无奈的是下一步

$$2z+1=(2k+1)(2y+1)$$
$$z+1=(k+1)(2y+1)$$

由第二个式子，$z+1$不含任何奇数因子，否则就能被构造出来，显然此时 $z=2^n-1$

由第一个式子，如果 $2^{n+1}-1$能被两个 $>1$的奇数相乘表示出来就会 $gg$，显然这个数没有 $2$的因子，所以只有当它自己本身是个素数的时候才能不被构造出来

综上所述，当 $2^{n+1}-1$是素数的时候，$2^n-1$就是一个解

然后这就是梅森素数～_～

自闭了这推导可能是神仙，或者说我初等数论姿势太低了 $qwq$

#include <cstdio>
#include <vector>
#include <algorithm>
#define fo(i, a, b) for (int i = a; i <= b; ++i)
#define mod 1000000007
#define ll long long
const int a[40] = {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};
inline ll pow (ll x, int y)
{
    ll ret = 1;
    if (y < 0) return 0;
    while (y)
    {
        if (y & 1) ret = ret * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ret;
}
int n; 
int main() {
    scanf("%d", &n);
    printf("%lld", pow(2, a[n - 1] - 1) - 1);
    return 0;
}