首页 > 试题广场 >

小苯的数字权值

[编程题]小苯的数字权值

热度指数：1446 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小苯定义一个数字的权值为：该数字的正因子个数。
小苯现在拿到了一个正整数 $x$ ，他希望将 $x$ 分解为若干不等于 $1$ 的数字（也可以不做分解），使得所有分解出的正整数乘积等于 $x$ ，且所有数字的权值之和尽可能大，你能帮帮他求出最大的权值和吗。

输入描述:

输入包含  行。
第一行一个正整数 ，表示数据组数。
接下来  行，每行一个正整数 ，表示每组数据中小苯询问的数字 。

输出描述:

输出包含  行，每行一个正整数表示每组测试数据的最大权值和。

示例1

输入

输出

2
4
4

说明

第一个测试数据中，无法分解，直接取  的权值为 。
第二个测试数据中，将  分解为 ，权值和为 。

算法知识视频讲解

牛客401767243号

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

const int MAX = 200001;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Step 1: 预处理每个数的因子个数
    int num_factors[MAX] = {0};
    for (int i = 1; i < MAX; ++i) {
        for (int j = i; j < MAX; j += i) {
            num_factors[j]++;
        }
    }

    // Step 2: 初始化 DP 数组
    int dp[MAX];
    for (int i = 2; i < MAX; ++i) {
        dp[i] = num_factors[i]; // 初始为自己不做分解的情况
    }

    // Step 3: DP 更新最优解
    for (int i = 2; i < MAX; ++i) {
        for (int j = 2; j <= MAX / i; ++j) {
            int product = i * j;
            if (product < MAX) {
                dp[product] = max(dp[product], dp[i] + dp[j]);
            }
        }
    }

    // Step 4: 读取输入并输出结果
    int T;
    cin >> T;
    while (T--) {
        int x;
        cin >> x;
        cout << dp[x] << '\n';
    }

    return 0;
}

发表于 2025-06-12 17:28:06 回复(0)