梅森素数
Problem:120
Time Limit:1000ms
Memory Limit:65536K
Description
由于梅森学识渊博，才华横溢，为人热情以及最早系统而深入地研究2p－1 型的数（其中p为素数），为了纪念他，数学界就把这种数称为“梅森数”；并以Mp 记之（其中M为梅森姓名的首字母），即Mp=2p-1 。如果梅森数为素数，则称之为“梅森素数”。 比如p＝2，3，5，7时，Mp都是素数，但211-1 不是素数 。现在请你求出前N个梅森素数。
Input
有多组测试数据。
第一行是一个正整数T，表示测试数据的组数。接下来每组1个数p的值，这里2<= p <= 62。
Output
对于每组测试数据，判断Mp 是不是梅森素数，是就输出“yes ”，否就输出“no”，输出后要换行。
Sample Input
2
2
7
Sample Output
yes
yes
这是卢卡斯-莱默判定法的模板题
#include <cstdio>
typedef long long ll;
ll lucy(ll a,ll b,ll mode)
{ll ans=0;while(b){if(b&1)ans=(ans+a)%mode;b>>=1;a=(a<<1)%mode;}return ans;}
int main()
{int t;scanf("%d",&t);while(t --){int p;scanf("%d",&p);ll n=((ll)1<<p)-1;ll r= 4;if(p==2)printf("yes\n");else{while((--p)!=1)r= (lucy(r,r,n)+n-2)%n;if(r%n==0)printf("yes\n");elseprintf("no\n");}}return 0;
}