codeforces 225E E. Unsolvable(梅森素数+数学)

题目链接：

codeforces 225E

题目大意：

给出一个等式， z=[x2]+y+x⋅y ，求另这个等式无解的z，从小到大排序，访问第i个。

题目分析：

• 首先为了简便计算先要通过分奇偶去掉向下取整符号，原式转换为如下形式：
  
  {z=k+y+2ky ,x=2kz=k+y+(2k+1)⋅y ,x=2k+1(1)(2)
• 对于(1)式我们采取如下推到过程进行推导：
  
  z=k+y+2ky,k>=0⇒2z+1=2k+2y+4ky+1⇒2z+1=(2k+1)⋅(2y+1)(3)
• 对于(2)式我们采取如下的推导过程进行推导：
  
  z=k+y+(2k+1)⋅y，k≥0⇒z+1=k+2y+2ky+1⇒z+1=(k+1)⋅(2y+1)(4)
• 那么由(4)式得，要想让原式无解，我们能够知道2y+1能够构造出所有的奇数，k+1能够造出所有正整数，任意正整数可以分解为 k⋅2t,k是一个奇数 ,因为2y+1能够构造所有大于1的奇数，所以对于2^t的数是不能构造的，所以 z=2t−1
• 那么由(3)式得，要想让原式无解，我们能够知道2y+1和2k+1能够构造出所有大于1的奇数，判断当前的式子对于(4)不能够构建的 2t−1 , 2z+1=2⋅(2t−1)+1=2t+1−1 ,发现一定是个奇数，两个大于1的奇数，一定能够构造出所有非素数的奇数，因为奇数乘奇数一定还是奇数，素数不能分解为两个大于1的因数，所以斯说 2t+1−1为素数的2t−1的z不能构造
• 所以另 z=2t−1,2t+1−1 是梅森素数，打一个表就可以得到所有梅森素数的t+1，然后得到t，算出40个梅森素数即可

AC代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL mod = 1e9+7;
int a[45] = {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};
int n;
LL pp ( LL num , LL x )
{
LL ret = 1;
while ( x )
{
if ( x&1 )
{
ret *= num;
ret %= mod;
}
num *= num;
num %= mod;
x >>= 1;
}
return ret;
}
int main ( )
{
while ( ~scanf ( "%d" , &n ) )
{
printf ( "%I64dn" , pp ( 2 , a[n-1]-1 ) -1 );
}
}

最后

以上就是体贴保温杯为你收集整理的codeforces 225E E. Unsolvable(梅森素数+数学)的全部内容，希望文章能够帮你解决codeforces 225E E. Unsolvable(梅森素数+数学)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。