pollard_rho和Miller

pollard_rho和Miller_Rabin

Miller_Rabin就是以概论大小来判断素数可以判断2^63范围的数
pollard_rho推荐两个很好的博客来理解：整数分解费马方法以及Pollard rho和[ZZ]Pollard Rho算法思想
  1 //#pragma comment(linker, "/STACK:167772160")//手动扩栈~~~~hdu 用c++交
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cstdlib>
  5 #include<iostream>
  6 #include<queue>
  7 #include<stack>
  8 #include<cmath>
  9 #include<set>
 10 #include<algorithm>
 11 #include<vector>
 12 #include<malloc.h>
 13 using namespace std;
 14 #define clc(a,b) memset(a,b,sizeof(a))
 15 #define inf 0x3f3f3f3f
 16 #define LL long long
 17 const double eps = 1e-5;
 18 const double pi = acos(-1);
 19 // inline int r(){
 20 //     int x=0,f=1;char ch=getchar();
 21 //     while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
 22 //     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 23 //     return x*f;
 24 // }
 25 const int Times = 10;
 26 const int N = 5500;
 27 
 28 LL ct, cnt;
 29 LL fac[N], num[N];//fac记录素因子，num记录每个因子的次数
 30 
 31 LL gcd(LL a, LL b)
 32 {
 33     return b? gcd(b, a % b) : a;
 34 }
 35 //return a*b%m
 36 LL multi(LL a, LL b, LL m)
 37 {
 38     LL ans = 0;
 39     a %= m;
 40     while(b)
 41     {
 42         if(b & 1)
 43         {
 44             ans = (ans + a) % m;
 45             b--;
 46         }
 47         b >>= 1;
 48         a = (a + a) % m;
 49     }
 50     return ans;
 51 }
 52 
 53 LL quick_mod(LL a, LL b, LL m)
 54 {
 55     LL ans = 1;
 56     a %= m;
 57     while(b)
 58     {
 59         if(b & 1)
 60         {
 61             ans = multi(ans, a, m);
 62             b--;
 63         }
 64         b >>= 1;
 65         a = multi(a, a, m);
 66     }
 67     return ans;
 68 }
 69 //判断素数
 70 bool Miller_Rabin(LL n)
 71 {
 72     if(n == 2) return true;
 73     if(n < 2 || !(n & 1)) return false;
 74     LL m = n - 1;
 75     int k = 0;
 76     while((m & 1) == 0)
 77     {
 78         k++;
 79         m >>= 1;
 80     }
 81     for(int i=0; i<Times; i++)
 82     {
 83         LL a = rand() % (n - 1) + 1;
 84         LL x = quick_mod(a, m, n);
 85         LL y = 0;
 86         for(int j=0; j<k; j++)
 87         {
 88             y = multi(x, x, n);
 89             if(y == 1 && x != 1 && x != n - 1) return false;
 90             x = y;
 91         }
 92         if(y != 1) return false;
 93     }
 94     return true;
 95 }
 96 //分解素数
 97 LL pollard_rho(LL n, LL c)
 98 {
 99     LL i = 1, k = 2;
100     LL x = rand() % (n - 1) + 1;
101     LL y = x;
102     while(true)
103     {
104         i++;
105         x = (multi(x, x, n) + c) % n;
106         LL d = gcd((y - x + n) % n, n);
107         if(1 < d && d < n) return d;
108         if(y == x) return n;
109         if(i == k)
110         {
111             y = x;
112             k <<= 1;
113         }
114     }
115 }
116 
117 void find(LL n, int c)
118 {
119     if(n == 1) return;
120     if(Miller_Rabin(n))
121     {
122         fac[ct++] = n;
123         return ;
124     }
125     LL p = n;
126     LL k = c;
127     while(p >= n) p = pollard_rho(p, c--);
128     find(p, k);
129     find(n / p, k);
130 }
131 
132 int main()
133 {
134     LL n;
135     while(cin>>n)
136     {
137         ct = 0;
138         find(n, 120);
139         sort(fac, fac + ct);
140         num[0] = 1;
141         int k = 1;
142         for(int i=1; i<ct; i++)
143         {
144             if(fac[i] == fac[i-1])
145                 ++num[k-1];
146             else
147             {
148                 num[k] = 1;
149                 fac[k++] = fac[i];
150             }
151         }
152         cnt = k;
153         for(int i=0; i<cnt; i++)
154             cout<<fac[i]<<"^"<<num[i]<<" ";
155         cout<<endl;
156     }
157     return 0;
158 }
View Code