[Leaf] [P3861] 拆分

p3861-拆分---洛谷">P3861 拆分 - 洛谷

1. 题面梗概

中译中：给定 $n$，求将 $n$ 分解为若干个 互不相同 且 大于等于 2 的整数乘积的方案数。

$n \le 10^{12}, T \le 5$，结果模 $998244353$。

$688 = 2 \times 4 \times 86 = 2 \times 8 \times 43 = 2 \times 344 = 4 \times 172 = 8 \times 86 = 16 \times 43$

2. 逻辑推导

由于 $n \leq 10^{12}$，显然线性的 $O(n)$ 做法也被卡了，我们得从 $O( \sqrt{ n })$ 的规模入手。

虽然 $n$ 的因数个数 $d(n)$ 却不大（ $10^{12}$ 这个规模，$d(n)$ 最大只有 $6720$ ）。

既然是个计数类问题，我们不妨用 DP 来计数：

2.1 状态

如果求的是 "和为 $n$ "，我们可以直接套 0/1 背包，本题要求乘法，不过也类似。

定义状态： $dp[i][j]$ 表示使用前 $j$ 个约数（即 $fac[2 \dots j]$，跳过 1），使得乘积恰好等于第 $i$ 个约数 $fac[i]$ 的方案数。

对于每一个状态 $dp[i][j]$，我们考虑第 $j$ 个约数 $f = fac[j]$ 的选取情况：

1. 不选 $fac[j]$：方案数继承自前 $j-1$ 个约数的结果。

$$dp[i][j] = dp[i][j-1]$$

2. 选 $fac[j]$（前提是 $fac[i]$ 能被 $f$ 整除）： 我们需要凑出剩余的乘积 $fac[i] / f$，且只能使用前 $j-1$ 个约数（以保证互不相同）。

$$dp[i][j] = (dp[i][j-1] + dp[id(fac[i]/f)][j-1]) \pmod{mod}$$

2.2 映射技巧

由于 $fac[i]/f$ 是一个具体的数值，我们需要 $O(1)$ 找到它在 fac 数组中的下标。

利用 $n/x$ 的分布特性，通过 pos1（处理 $\le \sqrt{n}$）和 pos2（处理 $> \sqrt{n}$）双数组映射来优化，防止数组开太大。

3. 代码实现

▶

AcCode

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxm = 6720 + 5;
const int maxn = 1e6 + 5;
const int mod = 998244353;

int dp[maxm][maxm];
// dp[i][j]：使用前 j 个因数，乘积为 fac[i] 的方案数
ll fac[maxm];
int pos1[maxn], pos2[maxn], cnt;
ll n, sq;

// 映射函数 x -> fac 下标
int get( ll x )
{
    if( x <= sq ) return pos1[x];
    else return pos2[n / x];
}

void solve( )
{
    cin >> n;
    sq = (ll)sqrt( n );
    cnt = 0;
    for( ll i = 1; i * i <= n; ++ i )
    {
        if( n % i == 0 )
        {
            fac[++ cnt] = i;
            if( i * i != n ) fac[++ cnt] = n / i;
        }
    }
    sort( fac + 1, fac + cnt + 1 );

    for( int i = 1; i <= cnt; ++ i )
    {
        if( fac[i] <= sq ) pos1[ fac[i] ] = i;
        else pos2[ n / fac[i] ] = i;
        for( int j = 1; j <= cnt; ++ j ) dp[i][j] = 0;
    }
	
	// 初始化
    for( ll j = 0; j <= cnt; ++ j ) dp[1][j] = 1;
	
	// 外层 j 遍历可选因数 fac[j]
    for( ll j = 2; j <= cnt; ++ j )
    {
        ll f = fac[j];
        // 内层 i 遍历目标乘积 fac[i]
        for( ll i = 2; i <= cnt; ++ i )
        {   // 0/1 背包
	        // 不选
            dp[i][j] = dp[i][j - 1];
            // 选
            if( fac[i] % f == 0 )
                dp[i][j] = ( dp[i][j] + dp[ get( fac[i] / f ) ][j-1] ) % mod;
        }
    }
    // 最后除掉一个空集
    ll ans = dp[cnt][cnt] - 1;
    cout << ( ans + mod ) % mod << '\n';
}

int main( )
{
    ios::sync_with_stdio(0); cin.tie(0);
    int _t = 1; cin >> _t;
    while( _t -- ) solve( );
    return 0;
}

4. 复盘

• 复杂度分析：$O( T \cdot d(n)^2 )$。

• 碎碎念：数论下的 计数类 DP，关键还是分析性质，找到转移关系。

• 关联笔记：[[初等数论]] | [[计数DP]]