给定一个正整数 ，试快速找到它的一个 非平凡因数。

考虑朴素算法，因数是成对分布的， 的所有因数可以被分成两块，即 和 。只需要把 里的数遍历一遍，再根据除法就可以找出至少两个因数了。这个方法的时间复杂度为 。

当 时，这个算法的运行时间我们是无法接受的，希望有更优秀的算法。一种想法是通过随机的方法，猜测一个数是不是 的因数，如果运气好可以在 的时间复杂度下求解答案，但是对于 的数据，成功猜测的概率是 , 期望猜测的次数是 。如果是在 里进行猜测，成功率会大一些。我们希望有方法来优化猜测。

最简单的算法即为从 进行遍历。

我们能够证明 result 中的所有元素均为 N 的素因数。

首先证明元素均为 的素因数：因为当且仅当 N % i == 0 满足时，result 发生变化：储存 ，说明此时 能整除 ，说明了存在一个数 使得 ，即 （其中， 为 自身发生变化后遇到 时所除的数。我们注意到 result 若在 push 之前就已经有数了，为 ，那么有 N ，被除的乘积即为 ）。所以 为 的因子。

其次证明 result 中均为素数。我们假设存在一个在 result 中的合数 ，并根据整数基本定理，分解为一个素数序列 ，而因为 ，所以它一定会在 之前被遍历到，并令 while(N % k1 == 0) N /= k1，即让 N 没有了素因子 ，故遍历到 时，N 和 已经没有了整除关系了。

值得指出的是，如果开始已经打了一个素数表的话，时间复杂度将从 下降到 。去 筛法 处查阅更多打表的信息。

例题：CF 1445C

而下面复杂度复杂度更低的 Pollard-Rho 算法是一种用于快速分解非平凡因数的算法（注意！非平凡因子不是素因子）。而在此之前需要先引入生日悖论。

不考虑出生年份（假设每年都是 365 天），问：一个房间中至少多少人，才能使其中两个人生日相同的概率达到 ?

解：假设一年有 天，房间中有 人，用整数 对这些人进行编号。假定每个人的生日均匀分布于 天之中，且两个人的生日相互独立。

设 个人生日互不相同为事件 , 则事件 的概率为

至少有两个人生日相同的概率为 。根据题意可知 , 那么就有

由不等式 可得

因此

将 代入，解得 。所以一个房间中至少 人，使其中两个人生日相同的概率达到 , 但这个数学事实十分反直觉，故称之为一个悖论。

当 ， 时，出现两个人同一天生日的概率将大于 1。那么在一年有 天的情况下，当房间中有 个人时，至少有两个人的生日相同的概率约为 。

考虑一个问题，设置一个数据 ，在 里随机选取 个数（ 时就是它自己），使它们之间有两个数的差值为 。当 时成功的概率是 ，当 时成功的概率是 （考虑绝对值， 可以取 或 ），随着 的增大，这个概率也会增大最后趋向于 1。

和某个数的最大公约数一定是 的约数，即 ，只要选适当的 使得 ，就可以求得 的一个约数 。满足这样条件的 不少， 有若干个质因子，每个质因子及其大部分倍数都是可行的。

我们通过 来生成一个序列 ：随机取一个 ，令 。其中 是一个随机选取的常数。

举个例子，设 ， 生成的数据为

可以发现数据在 以后都在 之间循环。如果将这些数如下图一样排列起来，会发现这个图像酷似一个 ，算法也因此得名 rho。

选择 这个函数生成序列，是因为它有一个性质：，其中 。

若 ，则可以将它们表示为 ，，满足 。

，因此 ，其中 。

同理，，因此 。

根据生日悖论，生成的序列中不同值的数量约为 个。设 为 的最小非平凡因子，显然有 。

将 中每一项对 取模，我们得到了一个新序列 （当然也可以写作 ），并且根据生日悖论可以得知新序列中不同值的个数约为 。

因此，我们可以期望在 的时间内找到两个位置 ，使得 ，这意味着 ，我们可以通过 获得 的一个非平凡因子。

同理，任何满足 的函数 （例如多项式函数）都可以用在此处，且我们希望它对大部分初始值尽可能快地进入循环、循环周期尽可能短（但对于一个合数与其任一质因子，循环周期长度不能相同，否则 Pollard Rho 算法将无法分离出这个因子）。

一般选择 生成序列，原因是它满足上述条件，且运行效率较高。同时，每次调用函数都将 设置为随机常数可以保证分解失败后重新分解的成功率。

我们期望枚举 个 来分解出 的一个非平凡因子 ，因此。Pollard-rho 算法能够在 的期望时间复杂度内分解出 的一个非平凡因子，通过上面的分析可知 ，那么 Pollard-rho 算法的总时间复杂度为 。

下面介绍两种实现算法，两种算法都可以在 的时间复杂度内完成。

假设两个人在赛跑，A 的速度快，B 的速度慢，经过一定时间后，A 一定会和 B 相遇，且相遇时 A 跑过的总距离减去 B 跑过的总距离一定是圈长的 n 倍。

设 ，每一次更新 ，只要检查在更新过程中 a、b 是否相等，如果相等了，那么就出现了环。

我们每次令 ，判断 d 是否满足 ，若满足则可直接返回 。由于 是一个伪随机数列，必定会形成环，在形成环时就不能再继续操作了，直接返回 n 本身，并且在后续操作里调整随机常数 ，重新分解。

使用 求解的时间复杂度为 ，频繁地调用会使算法运行地很慢，可以通过乘法累积来减少求 的次数。如果 ，则有 ，，并且由 欧几里得算法 有 。

我们每过一段时间将这些差值进行 运算，设 ，如果某一时刻得到 那么表示分解失败，退出并返回 本身。每隔 个数，计算是否满足 。此处取 ，可以根据实际情况进行调节。

注意到在环上更容易分解出因数，我们可以先迭代一定的次数。

例题：P4718【模板】Pollard-Rho 算法

对于一个数 ，用 Miller Rabin 算法 判断是否为素数，如果是就可以直接返回了，否则用 Pollard-Rho 算法找一个因子 ，将 除去因子 。再递归分解 和 ，用 Miller Rabin 判断是否出现质因子，并用 max_factor 更新就可以求出最大质因子了。由于这个题目的数据过于庞大，用 Floyd 判环的方法是不够的，这里采用倍增优化的方法。

https://en.wikipedia.org/wiki/Birthday_problem#Reverse_problem ↩