Codeforces225E - Unsolvable

Description

求所有对于方程$$z=\left \lfloor \frac{x}{2} \right \rfloor+y+xy$$不存在正整数解$(x,y)$的$z$中，第$n$小的$z$。答案对$10^9+7$取模。

Solution

$\left \lfloor \dfrac{x}{2} \right \rfloor$看起来很烦，来把它去掉。

$x$为奇数时，原方程可化为$2z+2= (2y+1)(x+1)$，其中$2y+1$是奇数，$x+1$是偶数。也就是说，$z$有解$\Leftrightarrow 2z+2$可以表示为奇数(非$1$)与偶数的积。那么$2z+2$就不能含有任何的奇数质因子，只能是$2$的若干次幂，这是$z$无解的必要条件。

$x$为偶数时，原方程可化为$2z+1= (2y+1)(x+1)$，其中$2y+1$是奇数，$x+1$是奇数。也就是说，$z$有解$\Leftrightarrow 2z+1$可以表示为奇数(非$1$)与奇数(非$1$)的积。那么$2z+1$作为一个奇数却不能表示成两个奇数的积，那么它只能是一个奇质数。这是$z$无解的另一个必要条件。

总结一下，$z$无解$\Leftrightarrow 2z+2=2^k, 2z+1$为质数$\Leftrightarrow 2z+1=2^k-1$且为质数

形如$2^k-1$的素数称为梅森素数(Mersenne prime)，目前仅发现50个梅森素数，最大的是$2^{77232917}-1$，有$23249425$位数。百度一下即可（摔！！！！！题解就是叫你上网查！！！！！）

Prime numbers like $2^{a-1}$ are Mersenne primes. Only about 46 such numbers are found now. Powers of 2 for the firts 40 numbers you can find for example here.

Code

//Unsolvable

#include <cstdio>

typedef long long lint;

lint const H=1e9+7;

int p[50]={0,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,25964951,30402457,32582657,37156667};

int m[50]={0,1,3,15,63,4095,65535,262143,73741816,536396503,140130950,487761805,319908070,106681874,373391776,317758023,191994803,416292236,110940209,599412198,383601260,910358878,532737550,348927936,923450985,470083777,642578561,428308066,485739298,419990027,287292016,202484167,389339971,848994100,273206869,853092282,411696552,876153853,90046024,828945523,697988359,761934284,490117835,345345628,545328622,969088513};

int main()

{

    int n; scanf("%d",&n);

    printf("%d\n",m[n]);

    return 0;

}

P.S.

自己上网查是什么鬼啊！！！！！

巴特西

Codeforces225E - Unsolvable

Description

Solution

Code

P.S.

最新文章

热门文章