1702 素数判定 2

 

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 钻石 Diamond

 

题目描述 Description

一个数，他是素数么？

设他为P满足(P<=2⁶³-1)

 

输入描述 Input Description

P

 

输出描述 Output Description

Yes|No

 

样例输入 Sample Input

2

 

样例输出 Sample Output

Yes

 

数据范围及提示 Data Size & Hint

算法导论——数论那一节

注意Carmichael Number

 

分析 Analysis

Miller-Rabbin 素数判定的裸题。这道题没法跑暴力了= =逼你用MRTD。

如果半数测试点没有AC，请检查计算过程中会不会溢出。需要快速乘法。

现在MRTD有很多种= = . 有的是没有TD (Twice Detect二次探测) 的, 然而标配是有的；有的是用质数做算子，有的是用随机数做算子的。

至于算子问题，要求算子与被测数互质。这个条件显然是限制被测数而不是算子的。

因为如果被测数为素数的话，它必然与比他小的所有数互质。

而如果算子是质数。。。可能效果会差点吧？其实也不会怎么样。

无关对错的问题，都是风格。

 

代码 Code

1 #include
           
             2 #include
            
              3 #include
             
               4 #include
              
                5 #define LL long long  6 using namespace std; 7  8 const int prime[10] = {
         2,3,5,7,11,13,17,19,23,29};  9 10 LL ksmul(LL a,LL b,LL m){11     if(!b) return 0;12     if(b == 1) return a;13     LL c = 0;14     while(b){15         if(b&1) c = (c+a)%m;16         a = (a+a)%m;17         b >>= 1;18     }19     return c;20 }21 22 LL ksm(LL a,LL k,LL m){23     if(!k) return 1;24     if(k == 1) return a%m;25     LL b = 1;26     while(k){27         if(k&1) b = ksmul(a,b,m);28         a = ksmul(a,a,m);29         k >>= 1;30     }31     return b;32 }33 34 bool TD(LL x,LL pri){35     if(x == pri) return true;36     LL m = x-1;37     while(!(m%2)) m >>= 1;38     LL y = ksm(pri,m,x);39     while(m != x-1 && y != 1 && y != x-1)40         y = ksmul(y,y,x),m <<= 1;41     return (m&1 || y == x-1);42 }43 44 bool MR(LL x){45     if(x == 2) return true;46     if(x < 2 || x % 2 == 0) return false;47     for(int i = 0;i < 10;i++){48         if(!TD(x,prime[i])) return false; 49     }50     return true;51 }52 53 int main(){54     LL x;55     scanf("%lld",&x);56     57     if(MR(x)) printf("Yes");58     else printf("No"); 59     return 0;60 }