问题2620--梅什么森？

2620: 梅什么森？

[命题人 : ]
时间限制 : 1 sec  内存限制 : 128 MB

提交
解决: 7提交量: 72统计

题目描述

星仪之昭依稀的记得世上有一种叫梅什么森的数字，并且有相关的验证：
  • 假设M是梅什么森数字，那么M要满足以下关系：
  1. 存在一个质数p，并且2p-1=M
  2. 设s=4，令s=(s*s-2)%M运算p-2次
如果最后这个s值为0，那么M就是梅什么森数，否则就不是。
现在请你编程解决，对于给定的一个数字，是否为这个梅什么森数。

输入

第一行一个T，表示接下来有T组数据  T<=1000
接下来T行，每行一个正整数表示待验证的数M。如果是，就输出1，否则输出0。M<=1145140

输出

T行表示答案

样例输入 Copy 

1
31

样例输出 Copy 

1

提示

取p为5，那么2p-1=31 √
设s=4，将s=(s*s-2)%M运算p-2次
第一次：s*s-2=14,s更新为14；
第二次：s*s-2=194,再对31取余得到8，s更新为8；
第三次：s*s-2=62,再对31取余得到0。
可以发现，p-2次操作后s最终为0，所以31是一个梅什么森数。
（为什么s初始化要是4？我也不知道）

来源/分类

 
提交