分解质因数

引入

给定一个正整数 ，试快速找到它的一个

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

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

朴素算法

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

=== "C++"

```cpp
list<int> breakdown(int N) {
  list<int> result;
  for (int i = 2; i * i <= N; i++) {
    if (N % i == 0) {  // 如果 i 能够整除 N，说明 i 为 N 的一个质因子。
      while (N % i == 0) N /= i;
      result.push_back(i);
    }
  }
  if (N != 1) {  // 说明再经过操作之后 N 留下了一个素数
    result.push_back(N);
  }
  return result;
}
```

=== "Python"

```python
def breakdown(N):
    result = []
    for i in range(2, int(sqrt(N)) + 1):
        if N % i == 0: # 如果 i 能够整除 N，说明 i 为 N 的一个质因子。
            while N % i == 0:
                N = N // i
                result.append(i)
    if N != 1: # 说明再经过操作之后 N 留下了一个素数
        result.append(N)
    return result
```

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

值得指出的是，如果开始已经打了一个素数表的话，时间复杂度将从 下降到 。去

例题：CF 1445C

Pollard Rho 算法

引入

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

生日悖论

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

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

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

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

由不等式 可得

然而我们可以得到一个不等式方程，，其中 是一个概率。

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

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

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

构造伪随机函数

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

随机取一个 ，令 ，在一定范围内可以认为这个数列是“随机”的。

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

可以发现数据在 3 以后都在 11,23,31 之间循环，这也是 被称为伪随机函数的原因。

如果将这些数如下图一样排列起来，会发现这个图像酷似一个 ，算法也因此得名 rho。

优化随机算法

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

将生日悖论应用到随机算法中，伪随机数序列中不同值的数量约为 个。设 为 的最小非平凡因子，显然有 。记 ，推导可得：

于是就得到了一个新序列 （当然也可以写作 )，并且根据生日悖论可以得知序列中不同值的个数约为 。

假设存在两个位置 ，使得 ，这意味着 , 因此我们可以通过 获得 的一个非平凡因子。

性质

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

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

实现

Floyd 判环

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

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

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

```cpp
ll Pollard_Rho(ll N) {
  ll c = rand() % (N - 1) + 1;
  ll t = f(0, c, N);
  ll r = f(f(0, c, N), c, N);
  while (t != r) {
    ll d = gcd(abs(t - r), N);
    if (d > 1) return d;
    t = f(t, c, N);
    r = f(f(r, c, N), c, N);
  }
  return N;
}
```

```python
def Pollard_Rho(N):
c = random.randint(0, 32767) % (N - 1) + 1
t = f(0, c, N)
r = f(f(0, c, N), c, N)
while t != r:
    d = gcd(abs(t - r), N)
    if d > 1:
        return d
    t = f(t, c, N)
    r = f(f(r, c, N), c, N)
return N
```

倍增优化

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

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

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

对于一个数 ，用