题意回顾

给定整数 $N$，质因子个数不超过 $6$。
统计所有满足条件的序列个数：

1. 序列中每个元素都是 $N$ 的因子（大于 $1$）
2. 当加入一个新数时，它与至多一个已存在序列中的数的 $\gcd > 1$

换句话说：序列中每个新元素最多只能与一个之前的元素共享质因子。

数据范围：$N \le 10^{15}$，质因子数 $k \le 6$。

---

关键分析与转化

1. 质因子表示

设 $N$ 的质因子分解为： [ N = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}, \quad k \le 6 ]

每个因子 $d$ 可以表示为： [ d = p_1^{b_1} p_2^{b_2} \dots p_k^{b_k}, \quad 0 \le b_i \le a_i ] 且 $d > 1$。

我们关心的是 $d$ 包含哪些质因子，即它的质因子集合 $S(d) \subseteq \{1, 2, \dots, k\}$。

---

2. 条件重新解释

条件"新数与至多一个已有数的公因子大于 $1$" 等价于：

对于新加入的因子 $d$，它的质因子集合 $S(d)$ 与已加入的所有因子的质因子集合的交集模式必须满足：
$S(d)$ 最多只能与一个连通块有交集。

这里"连通块"指的是：已加入的因子根据共享质因子关系形成的连通分量。

---

3. 状态设计

由于 $k \le 6$，我们可以用集合划分来表示当前状态。

设状态为当前已使用的质因子集合的一个划分 $\mathcal{P} = \{P_1, P_2, \dots, P_m\}$，其中：

• 每个 $P_i$ 是质因子索引的非空子集
• $P_i \cap P_j = \emptyset$ 对于 $i \neq j$
• $\bigcup P_i \subseteq \{1, 2, \dots, k\}$

这个划分表示：当前序列中，质因子形成的连通块情况。

---

4. 动态规划

定义 $dp[\mathcal{P}]$ 表示当前连通块划分为 $\mathcal{P}$ 时的序列方案数。

初始状态：空序列，$\mathcal{P} = \emptyset$，$dp[\emptyset] = 1$。

转移：考虑加入一个新因子 $d$，其质因子集合为 $S$：

• 如果 $S$ 与当前所有连通块都不相交（即 $S$ 是完全新的质因子），则形成一个新的连通块 $\{S\}$。
• 如果 $S$ 与恰好一个连通块 $P$ 有交集，则合并 $S$ 和 $P$ 形成新连通块。
• 如果 $S$ 与多个连通块有交集，则非法（违反条件）。

---

算法实现

步骤 1：质因子分解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;

vector<pair<ll, int>> factorize(ll n) {
    vector<pair<ll, int>> factors;
    for (ll p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            int cnt = 0;
            while (n % p == 0) {
                n /= p;
                cnt++;
            }
            factors.push_back({p, cnt});
        }
    }
    if (n > 1) factors.push_back({n, 1});
    return factors;
}

步骤 2：生成所有因子及其质因子集合

vector<int> generate_factors(const vector<pair<ll, int>>& factors) {
    int k = factors.size();
    vector<int> masks;  // 用bitmask表示质因子集合
    
    function<void(int, ll, int)> dfs = [&](int i, ll prod, int mask) {
        if (i == k) {
            if (prod > 1) masks.push_back(mask);
            return;
        }
        // 不选当前质因子
        dfs(i + 1, prod, mask);
        // 选当前质因子（至少一次）
        ll p = factors[i].first;
        int exp = factors[i].second;
        for (int e = 1; e <= exp; e++) {
            prod *= p;
            dfs(i + 1, prod, mask | (1 << i));
        }
    };
    
    dfs(0, 1, 0);
    return masks;
}

步骤 3：集合划分的表示和 DP

由于 $k \le 6$，贝尔数 $B_6 = 203$ 可接受。我们可以用整数编码表示划分。

// 将划分编码为整数
int encode_partition(const vector<int>& part) {
    int code = 0;
    for (int p : part) {
        code = (code << 4) | p;
    }
    return code;
}

// 解码
vector<int> decode_partition(int code) {
    vector<int> part;
    while (code > 0) {
        part.push_back(code & 15);
        code >>= 4;
    }
    reverse(part.begin(), part.end());
    return part;
}

// 计算答案
ll solve(ll N) {
    auto factors = factorize(N);
    int k = factors.size();
    auto factor_masks = generate_factors(factors);
    
    // 统计每种质因子集合的出现次数
    map<int, int> mask_count;
    for (int mask : factor_masks) {
        mask_count[mask]++;
    }
    
    // DP: state -> count
    map<int, ll> dp;
    dp[encode_partition({})] = 1;  // 初始空划分
    
    ll ans = 0;
    
    for (auto& [mask, cnt] : mask_count) {
        map<int, ll> new_dp = dp;
        
        for (auto& [code, val] : dp) {
            if (val == 0) continue;
            
            vector<int> part = decode_partition(code);
            int used_mask = 0;
            for (int p : part) used_mask |= p;
            
            // 情况1: mask与所有连通块不相交
            if ((mask & used_mask) == 0) {
                vector<int> new_part = part;
                new_part.push_back(mask);
                sort(new_part.begin(), new_part.end());
                int new_code = encode_partition(new_part);
                new_dp[new_code] = (new_dp[new_code] + val * cnt) % MOD;
            }
            
            // 情况2: mask与恰好一个连通块相交
            int intersect_count = 0;
            int intersect_idx = -1;
            for (int i = 0; i < part.size(); i++) {
                if (mask & part[i]) {
                    intersect_count++;
                    intersect_idx = i;
                }
            }
            
            if (intersect_count == 1) {
                vector<int> new_part;
                for (int i = 0; i < part.size(); i++) {
                    if (i == intersect_idx) {
                        new_part.push_back(part[i] | mask);
                    } else {
                        new_part.push_back(part[i]);
                    }
                }
                sort(new_part.begin(), new_part.end());
                int new_code = encode_partition(new_part);
                new_dp[new_code] = (new_dp[new_code] + val * cnt) % MOD;
            }
        }
        
        dp = new_dp;
    }
    
    // 累加所有状态的方案数
    for (auto& [code, val] : dp) {
        ans = (ans + val) % MOD;
    }
    
    return ans;
}

---

复杂度分析

• 质因子分解：$O(\sqrt{N})$，但 $N \le 10^{15}$ 可接受
• 生成因子：$O(2^k \cdot \text{max exponent})$，$k \le 6$ 很小
• DP 状态数：贝尔数 $B_k \le 203$
• 总复杂度：$O(B_k^2 \cdot 2^k)$，完全可接受

---

总结

本题的关键在于：

1. 问题转化：将因子序列条件转化为质因子连通块的限制
2. 状态设计：用集合划分表示质因子的连通情况
3. 动态规划：在划分状态空间上进行计数
4. 利用小参数：$k \le 6$ 使得贝尔数可接受

算法标签：动态规划、状压 DP、组合数学