Portal

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\)位数。百度一下即可(摔!!!!!题解就是叫你上网查!!!!!)

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.

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

05-06 18:11