1295. X的因子链

沉浸式做题过程

    首先分析题意。

输入正整数 X，求 X的大于 1 的因子组成的满足任意前一项都能整除后一项的严格递增序列的最大长度，以及满足最大长度的序列的个数。

初见题目：“任意前一项都能整除后一项的严格递增序列”是什么意思？（看不懂一点

看看样例：  输入样例：
            2
            3
            4
            10
            100
            输出样例：
            1 1
            1 1
            2 1
            2 2
            4 6

    我直接看到 100 对应4 6，再次分析：
    100 的大于 1 的因子有 2、4、5、10、20、25、50、100，而序列的最大长度为 4，还有 6 组这样的序列。
    不难想到，这些序列是跳过了某些因子（对应“任意”），并符合“严格递增”。


    再思考怎么才能得到这 6 个序列：
    注意到“整除”这一条件，序列中一定包含 100，也就是 X 本身，且 100 一定是位于序列的末尾。
    不妨从 100 向前枚举出符合条件的数。
    可以看作从 100 出发，不断展开分支。
    于是，可以写出这 6 个长度为 4 的序列（字典序大的在前）：

    1. 100、50、25、5
    2. 100、50、10、5
    3. 100、50、10、2
    4. 100、20、10、5
    5. 100、20、10、2
    6. 100、20、 4、2

    可以看出（递增）序列的终点总是 100，而起点可以是 2 或 5，
    且 2 和 5 都是小于 10 的质数。

    再次分解 100，
    100 = 1 * 100 = 2 * 50 = 4 * 25 = 5 * 20 = 10 * 10 = ···（后面的看作重复，10 也看作重复）
    再举例其他数，如 75：
    75 = 1 * 75 = 3 * 25 = 5 * 15 = ···
    可以得出规律：
    序列起点只能是非重复部分因数中的质数，也就是 X 的因子中小于 X^2 的质数。
    100 的起点是 2、5，且75的起点是3、5。

完善这份代码以完成上面的问题
#include <cmath>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

bool isPrime(int u) {
    if (u == 2) return true;  // 2是唯一的偶数质数
    if (u % 2 == 0) return false; // 排除偶数

    int sqrtN = static_cast<int>(sqrt(u));
    for (int i = 3; i <= sqrtN; i += 2) {
        if (u % i == 0) return false;
    }
    return true;
}

int main(){
    int X, len = 0, cnt = 0;
    while(scanf("%d", &X) != EOF){
        int n = sqrt((double)X);
        vector<int> fac, pfac;
        for(int i = 2; i <= X; i ++ ){
            if(!X % i){ // 找出 X 的所有大于 1 的因子
                fac.push_back(i);
            }
        }
        for(int j = 2; j < n; j ++ ){
            if( (!(X % j)) && isPrime(j) ){ // 找出 X 的所有大于 1 且小于 n 的质因子
                pfac.push_back(j);
            }
        }

        printf("%d %d\n", len, cnt);
    }

    return 0;
}

未完待续！！！！！