题解 | #小苯的数字权值#

题目链接

题目描述

定义一个正整数 $n$ 的权值 $\text{wt}(n)$ 为其正因子的数量。现在给定一个正整数 $x$ ，你可以将其分解为若干个大于 $1$ 的正整数的乘积，即 $x = p_1 \cdot p_2 \cdot \dots \cdot p_k$ 。你的目标是最大化这些因子的权值之和，即最大化 $\sum_{i=1}^{k} \text{wt}(p_i)$ 。

解题思路

本题要求找到一种分解方式，使得所有因子的权值（因子数量）之和最大。由于输入 $x$ 的范围不大（ $x \le 2 \cdot 10^5$ ），我们可以采用动态规划并预处理出所有可能答案。

问题分析与DP递推：对于一个数 $i$ ，我们可以选择不分解它，得到权值 $\text{wt}(i)$ ；或者将它分解。一个关键的洞察是，任何分解都可以看作是不断分离出质因子的过程。为了构建最优解，我们只需要考虑分离出最小质因子 (Smallest Prime Factor, SPF) 的情况。
- 定义状态：设 $dp[i]$ 是将数字 $i$ 进行最优分解后能获得的最大权值和。
- 状态转移方程：对于任何合数 $i$ ，其最优解是在“不分解”和“分离出最小质因子 $p=spf[i]$ ”这两种策略中取最优。
  - 不分解：价值为 $\text{wt}(i)$ 。
  - 分解：价值为 $dp[p] + dp[i/p]$ 。由于 $p$ 是质数，无法再分，dp[p] 就是 wt[p]=2。因此分解的价值是 $2 + dp[i/p]$ 。
  - 最终递推式为： $dp[i] = \max(\text{wt}(i), 2 + dp[i/spf[i]])$ 。
预处理步骤：
1. 预计算 wt 数组：使用 $\mathcal{O}(N \log N)$ 的筛法计算从 $1$ 到 $N$ 每个数的因子数量。
2. 预计算 spf 数组：使用 $\mathcal{O}(N \log \log N)$ 的线性筛法变体，计算从 $1$ 到 $N$ 每个数的最小质因子。
3. 计算 dp 数组：
  - 初始化 dp[i] = wt[i]。
  - 使用一个单重循环，从 i = 2 到 $N$ ，根据上述递推式 dp[i] = max(dp[i], 2 + dp[i/spf[i]]) 计算出所有 dp 值。因为计算 dp[i] 时，dp[i/spf[i]] 的值已经计算完毕，所以这个顺序是可行的。
处理查询：完成预处理后，对于每个查询 $x$ ，答案就是 dp[x]。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>

using namespace std;

const int MAX_X = 200005;
long long wt[MAX_X];
int spf[MAX_X];
long long dp[MAX_X];

void precompute() {
    for (int i = 1; i < MAX_X; ++i) {
        wt[i] = 0;
        spf[i] = i;
    }

    for (int i = 1; i < MAX_X; ++i) {
        for (int j = i; j < MAX_X; j += i) {
            wt[j]++;
        }
    }

    for (int i = 2; i * i < MAX_X; ++i) {
        if (spf[i] == i) { // i is a prime
            for (int j = i * i; j < MAX_X; j += i) {
                if (spf[j] == j) {
                    spf[j] = i;
                }
            }
        }
    }
    
    dp[1] = 0;
    for (int i = 2; i < MAX_X; ++i) {
        dp[i] = wt[i];
        if (spf[i] < i) { // i is composite
            dp[i] = max(dp[i], dp[spf[i]] + dp[i / spf[i]]);
        }
    }
}

void solve() {
    int x;
    cin >> x;
    cout << dp[x] << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    precompute();
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    static final int MAX_X = 200005;
    static long[] wt = new long[MAX_X];
    static int[] spf = new int[MAX_X];
    static long[] dp = new long[MAX_X];

    static {
        for (int i = 1; i < MAX_X; i++) {
            wt[i] = 0;
            spf[i] = i;
        }

        for (int i = 1; i < MAX_X; i++) {
            for (int j = i; j < MAX_X; j += i) {
                wt[j]++;
            }
        }
        
        for (int i = 2; i * i < MAX_X; i++) {
            if (spf[i] == i) { // i is a prime
                for (int j = i * i; j < MAX_X; j += i) {
                    if (spf[j] == j) {
                        spf[j] = i;
                    }
                }
            }
        }
        
        dp[1] = 0;
        for (int i = 2; i < MAX_X; i++) {
            dp[i] = wt[i];
            if (spf[i] < i) { // i is composite
                dp[i] = Math.max(dp[i], dp[spf[i]] + dp[i / spf[i]]);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int x = sc.nextInt();
            System.out.println(dp[x]);
        }
    }
}

import sys

MAX_X = 200001
wt = [0] * MAX_X
spf = [i for i in range(MAX_X)]
dp = [0] * MAX_X

def precompute():
    for i in range(1, MAX_X):
        for j in range(i, MAX_X, i):
            wt[j] += 1
    
    i = 2
    while i * i < MAX_X:
        if spf[i] == i: # i is prime
            for j in range(i * i, MAX_X, i):
                if spf[j] == j:
                    spf[j] = i
        i += 1
    
    dp[1] = 0
    for i in range(2, MAX_X):
        dp[i] = wt[i]
        if spf[i] < i: # i is composite
            dp[i] = max(dp[i], dp[spf[i]] + dp[i // spf[i]])

def main():
    precompute()
    t_str = sys.stdin.readline()
    if not t_str: return
    t = int(t_str)
    for _ in range(t):
        x_str = sys.stdin.readline()
        if not x_str: continue
        x = int(x_str)
        print(dp[x])

if __name__ == "__main__":
    main()

算法及复杂度

算法：动态规划、预处理、筛法
时间复杂度：预处理 wt 数组的复杂度为 $\mathcal{O}(N \log N)$ ，预处理 spf 数组的复杂度为 $\mathcal{O}(N \log \log N)$ ，计算 dp 数组的复杂度为 $\mathcal{O}(N)$ 。总时间复杂度由预处理主导，为 $\mathcal{O}(N \log N)$ 。每次查询的复杂度为 $\mathcal{O}(1)$ 。
空间复杂度：需要三个数组 wt, spf, dp 来存储预处理的结果，空间复杂度为 $\mathcal{O}(N)$ 。