做系统前怎么保存网站上的收藏/最新军事头条

$Pollard-Rho$ 算法是 John Pollard 发明的一种能快速找到大整数的一个非 $1$、非自身的因子的算法。

问题描述

分解一个合数 $n$ ，时间效率要求较高。

算法解决

生日悖论

在一个班级里，假设有 $60$ 人，所有人生日不同概率是多少？

依次按人考虑，第一个人有 $1$ 的概率，第二个人要与第一个人不同就是 $1-\frac{1}{365}$，第三个人与前两人不同，那么就是 $1-\frac{2}{365}$，那么第 $i$ 个人就是 $1-\frac{i-1}{365}$。

那么概率就是

$\prod _{i=1}^n(1-\frac{i-1}{365})=\prod _{i=0}^{n-1}\frac{365-i}{365}=\frac{365^{\underline{n}}}{365^n}$

假设我们带入 $n$ 等于 $60$，那么这个概率就是 $0.0058$，也就是说基本上不可能发生。

好像是因为和大众的常识有些违背，所以称作生日悖论。

假设一年有 $N$ 天，那么只要 $n\ge \sqrt{N}$ 存在相同生日的概率就已经大于 $50\%$ 了。

利用伪随机数判断

我们考虑利用之前那个性质来判断，生成了许多随机数，然后两两枚举判断。

假设枚举的两个数为 $i,j$，假设 $i>j$，那么判断一下 $\gcd (i-j,n)$ 是多少，如果非 $1$，那么我们就已经找出了一个 $n$ 的因子了，这样的概率随着枚举的组数变多会越来越快。

如果我们一开始把这些用来判断的数都造出来这样，这样就很坑了。

不仅内存有点恶心，而且其实效率也不够高。

考虑优化，我们用一个伪随机数去判断，不断生成两个随机数，然后像流水线一样逐个判断就行了。

有一个随机函数似乎很优秀，大部分人都用的这个：

$$f(x)=(x^2+a)\mathrm{m}\mathrm{o}\mathrm{d}n$$

$a$ 在单次判断中是一个常数。

然后一般这种简单的随机数都会出现循环节，我们判断一下循环节就行了。

但为了节省内存，需要接下来这种算法。

Floyd 判圈法

两个人同时在一个环形跑道上起跑，一个人是另外一个人的两倍速度，那么这个人绝对会追上另外一个人。追上时，意味着其中一个人已经跑了一圈了。

然后就可以用这个算法把退出条件变松，只要有环，我们就直接退出就行了。

如果这次失败了，那么继续找另外一个 $a$ 就行了。

代码实现

例题

$CODE$

#include <bits/stdc++.h>using namespace std;#define int __int128int ans;int read()
{int x = (int)0;char c = getchar();while (c < '0' || c > '9')c = getchar();while (c >= '0' && c <= '9'){x = x * (int)10 + c - '0';c = getchar();}return x;
}int abs(int x)
{if (x < (int)0)return -x;return x;
}void write(int x)
{if (x > (int)9)write(x / (int)10);putchar(x % (int)10 + '0');
}int randint(int l, int r)
{return (rand() % (r - l + 1) * rand() % (r - l + 1) + l % (r - l + 1)) % (r - l + 1);
}int gcd(int a, int b)
{if (b == 0)return a;return gcd(b, a % b);
}int qpow(int x, int y, int m)
{int r = 1ll;while (y){if (y & 1ll)r = r * x % m;x = x * x % m;y >>= 1ll;}return r;
}bool Miller_Rabin(int x)
{if (x < 3)return x == 2;if (x % 2 == 0)return false;int A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}, d = x - 1, r = 0;while (d % 2 == 0)d /= 2, ++r;for (auto a : A){int v = qpow(a, d, x);if (v <= 1 || v == x - 1)continue;for (int i = 0; i < r; ++i){v = (int)v * v % x;if (v == x - 1 && i != r - 1){v = 1;break;}if (v == 1)return false;}if (v != 1)return false;}return true;
}int Pollard_Rho(int N)
{if (N == 4)return 2;if (Miller_Rabin(N))return N;while (1){int c = randint(1, N - 1);auto f = [=](int x){ return ((int)x % N * x % N + c) % N; };int t = 0, r = 0, p = 1, q;do{for (int i = 0; i < 128; ++i){t = f(t), r = f(f(r));if (t == r || (q = (int)p * abs(t - r) % N) == 0)break;p = q;}int d = gcd(p, N);if (d > 1)return d;} while (t != r);}
}void max_prime_factor(int x)
{if (x <= ans || x < 2)return;int fac = Pollard_Rho(x);if (fac == x)ans = max(ans, x);elsemax_prime_factor(fac), max_prime_factor(x / fac);
}int T, n;signed main()
{T = read();while (T--){srand(time(0));n = read();ans = 1;max_prime_factor(n);if (ans == n){puts("Prime");}else{write(ans);putchar('\n');}}return 0;
}