首页 > 代码库 > SPOJ Prime or Not - 快速乘 - 快速幂
SPOJ Prime or Not - 快速乘 - 快速幂
Given the number, you are to answer the question: "Is it prime?"
Solutions to this problem can be submitted in C, C++, Pascal, Perl, Python, Ruby, Lisp, Hask, Ocaml, Prolog, Whitespace, Brainf**k and Intercal only.
Input
t – the number of test cases, then t test cases follows. [t <= 500]
Each line contains one integer: N [2 <= N <= 2^63-1]
Output
For each test case output string "YES" if given number is prime and "NO" otherwise.
Example
Input:523456Output:YESYESNOYESNO
题目大意是说，给你一个能够用有符号64位整型存储的数，判断它是否是素数。
用费马小定理，多次随机生成一个底数a，然后n - 1次幂，判断模n意义下是否是1。
为了充分表示对rand()的嫌弃，于是手写了一个随机数生成器。详细请见[here]
Code
1 /** 2 * SPOJ 3 * Problem#PON 4 * Accepted 5 * Time:180ms 6 * Memory:15360k 7 */ 8 #include<iostream> 9 #include<cstdio> 10 #include<cctype> 11 #include<cmath> 12 #include<ctime> 13 #include<cstring> 14 #include<cstdlib> 15 #include<fstream> 16 #include<sstream> 17 #include<algorithm> 18 #include<map> 19 #include<set> 20 #include<queue> 21 #include<vector> 22 #include<stack> 23 using namespace std; 24 typedef bool boolean; 25 #define INF 0xfffffff 26 #define smin(a, b) a = min(a, b) 27 #define smax(a, b) a = max(a, b) 28 template<typename T> 29 inline boolean readInteger(T& u){ 30 char x; 31 int aFlag = 1; 32 while(!isdigit((x = getchar())) && x != ‘-‘ && x != -1); 33 if(x == -1) { 34 ungetc(x, stdin); 35 return false; 36 } 37 if(x == ‘-‘){ 38 x = getchar(); 39 aFlag = -1; 40 } 41 for(u = x - ‘0‘; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - ‘0‘); 42 ungetc(x, stdin); 43 u *= aFlag; 44 return true; 45 } 46 47 #define LL long long 48 49 typedef class Random { 50 public: 51 unsigned int pre; 52 unsigned int seed; 53 54 Random():pre(0), seed((unsigned) time (NULL)) { } 55 Random(int seed):pre(0), seed(seed) { } 56 57 /** 58 * Generate a random number. 59 * @return this function will return the random number it gernerated 60 */ 61 unsigned int rand() { 62 // unsigned int ret = (seed * 7361238 + seed % 20037 * 1244 + pre * 12342 + 378211) * (seed + 134543); 63 // unsigned int ret = (seed * 7361238 + seed % 20037 * 1244 + pre * 12342 + 378211 + time(NULL) * pre) * (seed + 134543); 64 unsigned int ret; 65 if(ret & 1) 66 ret = (seed * 7361238 + seed % 20037 * 1245 + pre * 456451 + (time(NULL) * (pre * 5 + seed * 3 + 37)) + 156464); 67 else 68 ret = (seed * 7361238 + seed % 20037 * 1241 + pre * 456454 + (time(NULL) * (pre * 7 + seed * 3 + 18)) + 156464); 69 pre = seed; 70 seed = ret; 71 return ret; 72 } 73 }Random; 74 75 inline void setLLhighBit(long long& x, int a) { 76 int* p = (int*)&x; 77 *(p + 1) = a; 78 } 79 80 inline void setLLlowBit(long long& x, int a) { 81 int* p = (int*)&x; 82 *p = a; 83 } 84 85 inline void cleanLLSignFlag(long long& a) { 86 a &= (1ull << 63) - 1; 87 } 88 89 template<typename T> 90 T mul_mod(T a, T b, T& moder) { 91 if(b == 1) return a; 92 T temp = mul_mod(a, b >> 1, moder); 93 if(b & 1) return (((temp + temp) % moder) + a) % moder; 94 return (temp + temp) % moder; 95 } 96 97 template<typename T> 98 T pow_mod(T a, T pos, T& moder) { 99 if(pos == 1) return a;100 T temp = pow_mod(a, pos >> 1, moder);101 if(pos & 1) return mul_mod(mul_mod(temp, temp, moder), a, moder);102 return mul_mod(temp, temp, moder);103 }104 105 int T;106 LL n;107 Random r;108 109 inline void work() {110 readInteger(n);111 if((n & 1) == 0) {112 if(n == 2) puts("YES");113 else puts("NO");114 return;115 }116 unsigned int l, h;117 LL a, r1;118 for(int t = 0; t < 20; t++) {119 l = r.rand();120 h = r.rand();121 setLLhighBit(a, h);122 setLLlowBit(a, l);123 cleanLLSignFlag(a);124 a = (a % (n - 2)) + 2;125 r1 = pow_mod(a, n - 1, n);126 if(r1 != 1) {127 puts("NO");128 return;129 }130 }131 puts("YES");132 }133 134 int main() {135 readInteger(T);136 while(T--) {137 work();138 }139 return 0;140 }
SPOJ Prime or Not - 快速乘 - 快速幂
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。