Miller&&Pollard POJ 1811 Prime Test-白红宇

Miller&&Pollard POJ 1811 Prime Test

阅读量：5878 次

发布时间：2019-06-19

本文共 2805 字，大约阅读时间需要 9 分钟。

题意：素性测试和大整数分解， N (2 <= N < 2⁵⁴)。

分析：没啥好讲的，套个，POJ上C++提交

收获：写完这题得到模板

代码：

/************************************************* Author        :Running_Time* Created Time  :2015-8-28 13:02:38* File Name     :POJ_1811.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 1e5 + 10;const int S = 20;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;/* 素性测试，Miller_Rabin 随机算法 可以判断< 2^63的数 素数：true，合数：false*/const int S = 20; //随机算法判定次数，S越大，判错概率越小//非递归写法，递归写法可能会爆栈ll GCD(ll a, ll b) { if (a == 0) return 1; if (a < 0) a = -a; while (b) { ll c = a % b; a = b; b = c; } return a;}//计算 (a * b) % p，a，b是long long数，直接相乘可能会溢出ll multi_mod(ll a, ll b, ll p) { ll ret = 0; a %= p; b %= p; while (b) { if (b & 1) { ret += a; if (ret >= p) ret -= p; } a <<= 1; if (a >= p) a -= p; b >>= 1; } return ret;}//计算 a ^ x % pll pow_mod(ll a, ll x, ll p) { ll ret = 1; a %= p; while (x) { if (x & 1) ret = multi_mod (ret, a, p); a = multi_mod (a, a, p); x >>= 1; } return ret;}/* 以a为基,n-1=x*2^t，a^(n-1) = 1(mod n) 验证n是不是合数 一定是合数返回true, 不一定返回false*/bool check(ll a, ll n, ll x, int t) { ll ret = pow_mod (a, x, n); ll last = ret; for (int i=1; i<=t; ++i) { ret = multi_mod (ret, ret, n); if (ret == 1 && last != 1 && last != n - 1) return true; //合数 last = ret; } if (ret != 1) return true; return false;}bool Miller_Rabin(ll n) { if (n == 2) return true; if (n < 2 || ! (n & 1)) return false; //偶数或1 ll x = n - 1; int t = 0; while (! (x & 1)) { x >>= 1; t++; } for (int i=1; i<=S; ++i) { ll a = rand () % (n - 1) + 1; //需要cstdlib头文件 if (check (a, n, x, t)) return false; //合数 } return true;}/* 大整数分解，Pollard_rho 随机算法 factorize ()保存质因数在vector*/ll Pollard_rho(ll x, ll c) { ll i = 1, k = 2; ll a = rand () % x; ll b = a; while (1) { i++; a = (multi_mod (a, a, x) + c) % x; ll d = GCD (b - a, x); if (d != 1 && d != x) return d; if (b == a) return x; if (i == k) b = a, k += k; }}void factorize(ll n, vector
                      
                        &ret) { if (Miller_Rabin (n)) { //素数 ret.push_back (n); return ; } ll p = n; while (p >= n) p = Pollard_rho (p, rand () % (n - 1) + 1); factorize (p, ret); factorize (n / p, ret);}int main(void) { srand (time (NULL)); int T; scanf ("%d", &T); while (T--) { ll n; scanf ("%I64d", &n); if (Miller_Rabin (n)) puts ("Prime"); else { if (n <= 1) { puts ("-1"); continue; } vector
                       
                         ans; factorize (n, ans); sort (ans.begin (), ans.end ()); printf ("%I64d\n", ans[0]); // for (int i=0; i