Miiler-Robin素数测试与Pollard-Rho大数分解法
板题 Miiler-Robin素数测试目前已知分解质因数以及检测质数确定性方法就只能(sqrt{n})试除 费马小定理即我们耳熟能详的 二次探测原理对于质数(p),如果存在(x)满足 由此我们便可以随机生成多个(x),逐一用以上两个原理检验即可 bool Miller_Rabin(LL n){ if (n == 2 || n == 3 || n == 5 || n == 7 || n == 11 || n == 13) return true; if (n == 1 || n % 2 == 0 || n % 3 == 0 || n % 7 == 0 || n % 11 == 0 || n % 13 == 0) return false; int T = 50; LL t = n - 1,k = 0; while (!(t & 1)) t >>= 1,k++; while (T--){ LL x = qpow(random(n),t,n),y; REP(i,k){ y = x,x = mul(x,x,n); if (x == 1 && y != 1 && y != n - 1) return false; } if (x != 1) return false; } return true; } Pollard-Rho大数分解法我们利用式子(x^2 + c)伪随机生成两个数(a)和(b),判断(d = (a - b,n))是否大于(1)小于(n),如果是,我们便找打了一个(n)的因子(d),递归处理(frac{n}{d})和(d)即可,当我们使用以上的素数判定判定出(n)是质数时,计入答案 LL pr[maxn],pi; LL gcd(LL a,LL b){return b ? gcd(b,a % b) : a;} LL Pollard_Rho(LL n){ LL x = random(n),y = x,c = random(n),step = 1,t = 2; while (true){ step++; x = (mul(x,n) + c) % n; if (y == x) return 1; LL d = gcd((y - x + n) % n,n); if (d > 1) return d; if (step == t) y = x,t <<= 1; } } void Find(LL n){ if (n == 1) return; if (Miller_Rabin(n)) {pr[++pi] = n; return;} LL p = n; while (p == n) p = Pollard_Rho(n); Find(n / p); Find(p); } 至此我们就可以写出POJ1811 #include<algorithm> #include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<cmath> #include<map> #define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt) #define REP(i,n) for (int i = 1; i <= (n); i++) #define mp(a,b) make_pair<int,int>(a,b) #define cls(s) memset(s,sizeof(s)) #define cp pair<int,int> #define LL long long int using namespace std; const int maxn = 100005,maxm = 100005; const LL INF = 1000000000ll * 1000000000ll; inline LL read(){ LL out = 0,flag = 1; char c = getchar(); while (c < 48 || c > 57){if (c == ‘-‘) flag = -1; c = getchar();} while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();} return out * flag; } inline LL random(LL x){ LL re = 0; REP(i,4) re = (re << 14) + rand(); return re % x; } inline LL mul(LL a,LL b,LL P){ LL re = 0; for (; b; b >>= 1,a = (a + a) % P) if (b & 1) re = (re + a) % P; return re; } inline LL qpow(LL a,LL P){ LL re = 1; for (; b; b >>= 1,a = mul(a,a,P)) if (b & 1) re = mul(re,P); return re; } bool Miller_Rabin(LL n){ if (n == 2 || n == 3 || n == 5 || n == 7 || n == 11 || n == 13) return true; if (n == 1 || n % 2 == 0 || n % 3 == 0 || n % 7 == 0 || n % 11 == 0 || n % 13 == 0) return false; int T = 50; LL t = n - 1,n); if (x == 1 && y != 1 && y != n - 1) return false; } if (x != 1) return false; } return true; } LL pr[maxn],t <<= 1; } } void Find(LL n){ if (n == 1) return; if (Miller_Rabin(n)) {pr[++pi] = n; return;} LL p = n; while (p == n) p = Pollard_Rho(n); Find(n / p); Find(p); } int main(){ //srand(998244353); int T = read(); LL n; while (T--){ if (Miller_Rabin(n = read())) puts("Prime"); else { pi = 0; Find(n); //REP(i,pi) printf("%lld ",pr[i]); puts(""); if (pi == 1) {puts("Prime"); continue;} LL x = pr[1]; for (int i = 2; i <= pi; i++) x = min(x,pr[i]); printf("%lldn",x); } } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |