---
title: "x的因子链"
created: 2025-11-28
tags:
  - 算法
---

# x的因子链

## 题目 [X的因子链](https://www.acwing.com/problem/content/1297/)

![[image-dee7edc8.png]]

## 思路分析

本题用到这两个数论常用的算法：

**算术基本定理** 就是因式分解的定理，所有的整数都可以唯一分解成若干个质因子乘积的形式

$N=P\_1^{α1}×P\_2^{α2}×…×P\_k^{αk}$*，其中 Pi是质数，每一个*
$αi≥0$

![[image-f5106699.png]]

**筛法求素数——线性筛法（欧拉筛法）**

在O(N)的时间复杂度内，求出来1 ~ n中所有的质数，以及每一个数的最小质因子。

```cpp
void get_primes(){
    for(int i=2;i<=n;i++){
        if(!st[i])
            primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++){
            /*
            因为prime中素数是递增的，所以如果i%prime[j]!=0代表i的最小质因数还没有找到，
            即i的最小质因数大于prime[j]
            也就是说prime[j]就是i*prime[j]的最小质因数，于是i*prime[j]被它的最小质因数筛掉了
            */
            st[primes[j] * i] = true; // 把质数的i倍筛掉
            /*
            如果当i%prime[j]==0时，代表i的最小质因数是prime[j]，
            那么i*prime[j+k](k>0)这个合数的最小质因数就不是prime[j+k]而是prime[j]了
            所以i*prime[j+k]应该被prime[j]筛掉，而不是后续的prime[j+k]，于是在此时break
            */
            if (i % primes[j] == 0)
                break; // 通过最小质因子来筛
        }
    }
}
```

① 筛掉的一定是合数，且一定是用其最小质因子筛的

② 合数一定会被筛掉

![[image-ca1f8266.png]]

这样我们就可以把所有质数找出来，而且每个和数只会被最小质因子筛，所以每个和数只会被筛一次，所以整个算法的时间复杂度为O(N)

回归本题

题意有点绕，通俗来讲就是给我们任意一个正整数X，我们可以求一下X所有的约数：d1,d2…dk，

然后我们要从中挑出来一些严格单调递增的数

使得每一项都是它前一项的倍数：a1<a2<…<at (ai|ai+1)

然后问我们可以挑出来的序列的最大长度是多少，以及有多少个满足条件的单调递增的序列？

每一项必然满足：ai+1=ai⋅P(P是倍数且>1)，每一个后一项都等于前一项乘上一个倍数，那么我们要想让整个序列最长的话，要尽可能让倍数最小，最小只能小到质数，因为小到质数就不能再分了，因此就可以用我们上边的算术基本定理了，

假设X分解质因数的结果：$X=P1^{α1}×P2^{α2}×…×P\_k^{αk}$，我们可以发现一共有
α1+α2+…+αk 个质因子，因此我们每一次后一项要比前一项至少要多一个倍数，每一次的倍数必然是一个质数，必然是在X当中的某一个质因子，所以序列的最大长度就是
α1+α2+…+αk 那么如何求这样序列的个数呢？先做一个映射，我们不存数的本身，我们存数的增量，原序列是a1,a2…at，映射的序列是：a1,a2/a1,a3/a2,……，at/at-1，这两个序列是一一对应的，给我们第一个序列就可以求第二个序列，在第二个序列中每一个数都是X的质因子，因此序列个数就是X所有质因子的排列数。

![[image-583a17f9.png]]

排列数公式：

![[image-5bdeeaf0.png]]

也被称为多重集合的排列数问题，这样就避免了重复情况。

我们分解质因数就用线性筛法来解。

## 代码实现

```cpp
#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long LL;

const int N = (1 << 20) + 10;

int primes[N], cnt;

int minp[N];

bool st[N];

void get_primes(int n)

{

    for (int i = 2; i <= n; i ++ )

    {

        if (!st[i])

        {

            minp[i] = i;

            primes[cnt ++ ] = i;

        }

        for (int j = 0; primes[j] * i <= n; j ++ )

        {

            int t = primes[j] * i;

            st[t] = true;

            minp[t] = primes[j];

            if (i % primes[j] == 0) break;

        }

    }

}

int main()

{

    get_primes(N - 1);

    int fact[30], sum[N];

    int x;

    while (scanf("%d", &x) != -1)

    {

        int k = 0, tot = 0;

        while (x > 1)

        {

            int p = minp[x];

            fact[k] = p, sum[k] = 0;

            while (x % p == 0)

            {

                x /= p;

                sum[k] ++ ;

                tot ++ ;

            }

            k ++ ;

        }

        LL res = 1;

        for (int i = 1; i <= tot; i ++ ) res *= i;

        for (int i = 0; i < k; i ++ )

            for (int j = 1; j <= sum[i]; j ++ )

                res /= j;

        printf("%d %lld\n", tot, res);

    }

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[互质 欧拉函数|互质 欧拉函数]] 🏠 [[00-刷题理模型]] ➡️ [[分解质因数|分解质因数]]