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

小苯的数字权值

https://www.nowcoder.com/practice/aeacca655eec45999a6dc4d998dfd4a5

题目链接

HIGH7 小苯的数字权值

题目描述

给定一个正整数 x，你可以将其分解为 x = y_1 * y_2 * ... * y_k，其中 y_i > 1。我们定义一个数 n 的权值为其约数的个数，记作 wt(n)。请你找到一种分解方案，使得权值之和 wt(y_1) + wt(y_2) + ... + wt(y_k) 最大，并输出这个最大和。

解题思路

这是一个典型的动态规划问题。由于数据范围 x <= 2*10^5，我们可以预处理出所有可能答案。

1. 定义状态 我们定义一个数组 dp，其中 dp[i] 表示将数字 i 进行分解能够得到的最大权值和。我们的目标就是对于每个输入的 x，求出 dp[x]。

2. 状态转移 对于任何一个数 i，它的最优分解方案存在两种可能：

不分解：此时权值和就是它自身的权值，即 wt(i)。wt(i) 指的是 i 的约数个数。
分解：将 i 分解为两部分 j 和 k 的乘积，即 i = j * k。这种情况下，总的权值和就是这两部分分别取最优分解后的权值和之和，即 dp[j] + dp[k]。

综合这两种情况，dp[i] 的值应该是所有可能分解方案中的最大值。因此，状态转移方程为： dp[i] = max(wt(i), dp[j] + dp[i/j]) 其中 j 遍历 i 的所有约数。

3. 算法实现

预计算约数个数：首先，我们需要一个 wt 数组来存储从 1 到 2*10^5 每个数的约数个数。我们可以通过一个 $\mathcal{O}(N \log N)$ 的筛法来高效地完成：遍历 i 从 1 到 N_MAX，再将所有 i 的倍数 j 的 wt[j] 加一。
初始化DP数组：根据状态转移方程，dp[i] 的一个基础值就是不分解时的 wt[i]。所以我们首先令 dp[i] = wt[i]。
计算DP值：我们从小到大（i 从 2 到 2*10^5）进行计算。对于每个 i，我们遍历它的所有约数 j（从 2 到 sqrt(i) 即可），然后用 dp[j] + dp[i/j] 来尝试更新 dp[i]。 dp[i] = max(dp[i], dp[j] + dp[i/j])。
回答查询：完成预处理后，对于每个输入的 x，答案就是 dp[x]。

这个过程确保了在计算 dp[i] 时，所有比 i 小的数的 dp 值（如 dp[j] 和 dp[i/j]）都已经计算完毕，符合动态规划的最优子结构和无后效性原则。

代码

cpp
java
python

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

using namespace std;

const int N_MAX = 200005;
int wt[N_MAX];
long long dp[N_MAX];

void precompute() {
    // 1. 预计算所有数的约数个数
    for (int i = 1; i < N_MAX; ++i) {
        for (int j = i; j < N_MAX; j += i) {
            wt[j]++;
        }
    }

    // 2. 动态规划求解
    for (int i = 1; i < N_MAX; ++i) {
        dp[i] = wt[i]; // 初始化为不分解的情况
    }

    for (int i = 2; i < N_MAX; ++i) {
        for (int j = 2; j * j <= i; ++j) {
            if (i % j == 0) {
                // dp[i] = max(当前值, 分解为j和i/j后的最优解之和)
                dp[i] = max(dp[i], dp[j] + dp[i / j]);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    precompute();

    int t;
    cin >> t;
    while (t--) {
        int x;
        cin >> x;
        cout << dp[x] << endl;
    }
    return 0;
}

import java.util.Scanner;

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

    static {
        // 1. 预计算所有数的约数个数
        for (int i = 1; i < N_MAX; i++) {
            for (int j = i; j < N_MAX; j += i) {
                wt[j]++;
            }
        }

        // 2. 动态规划求解
        for (int i = 1; i < N_MAX; i++) {
            dp[i] = wt[i]; // 初始化为不分解的情况
        }
        
        for (int i = 2; i < N_MAX; i++) {
            for (int j = 2; j * j <= i; j++) {
                if (i % j == 0) {
                    dp[i] = Math.max(dp[i], dp[j] + dp[i / j]);
                }
            }
        }
    }

    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]);
        }
    }
}

N_MAX = 200005
wt = [0] * N_MAX
dp = [0] * N_MAX

# 1. 预计算所有数的约数个数
for i in range(1, N_MAX):
    for j in range(i, N_MAX, i):
        wt[j] += 1

# 2. 动态规划求解
for i in range(1, N_MAX):
    dp[i] = wt[i]  # 初始化为不分解的情况

for i in range(2, N_MAX):
    j = 2
    while j * j <= i:
        if i % j == 0:
            dp[i] = max(dp[i], dp[j] + dp[i // j])
        j += 1

# 读取输入并输出结果
t = int(input())
for _ in range(t):
    x = int(input())
    print(dp[x])

算法及复杂度

算法：动态规划、数论
时间复杂度： $\mathcal{O}(N \log N + N\sqrt{N})$ 。预计算约数个数需要 $\mathcal{O}(N \log N)$ ，DP计算过程需要 $\mathcal{O}(N\sqrt{N})$ ，其中 N 是数据范围 2*10^5。查询是 $\mathcal{O}(1)$ 。
空间复杂度： $\mathcal{O}(N)$ 。需要两个数组 wt 和 dp 来存储预处理的结果。