首页 > 试题广场 >

小苯的数字权值

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

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

$\hspace{15pt}$ 定义正整数 $n$ 的权值为 $n$ 的正因子的数量，即

$\operatorname{wt}(n)=\tau(n)$ ，

$\hspace{15pt}$ 其中 $\tau(n)$ 表示 $n$ 的因子个数。
$\hspace{15pt}$ 给定一个正整数 $x$ ，你可以将 $x$ 分解为若干个大于 $1$ 的正整数 $p_1,p_2,\dots,p_k$ （ $k\geqq1$ ），要求
$\hspace{23pt}\bullet\,$ $p_1\times p_2\times\dots\times p_k = x$ ；
$\hspace{23pt}\bullet\,$ 最大化

$\displaystyle \sum_{i=1}^{k} \operatorname{wt}(p_i)$ 。

$\hspace{15pt}$ 请你求出在最优分解下，上述表达式的最大可能值。

输入描述:

第一行输入一个整数  表示测试数据组数。 
此后  行，每行输入一个整数 。

输出描述:

对于每组数据，在一行上输出对应的最大权值和。

示例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)

牛客835777707号

题目有误： “定义正整数 n 的权值为 n 的正因子的数量” 。2的正因子只有它本身，故它的权值是 1，不是 2（个）。

发表于 2025-08-27 10:52:10 回复(1)

Python

慢热的杰尼龟在发动态

if __name__ == '__main__':
    val=[0]*200001
    for i in range(1,200001):
        # print("calc " + str(i))
        j = i
        while j < 200001:
            val[j]+=1
            j+=i

    calc=val

    for i in range(2,200001):
        for j in range(2,int(200001/i)):
            product=i*j
            if product < len(calc):
                if ((val[i] + val[j]) > calc[product]):
                    calc[product]=val[i] + val[j]

    count=int(input())
    for i in range(count):
        a=int(input())
        print("%d" %calc[a])

发表于 2025-06-21 00:01:33 回复(0)

versechen

技巧性太强了。面试挂。

发表于 2025-06-13 17:24:35 回复(0)

提交观点

问题信息

难度：

4条回答 106收藏 3250浏览

小苯的数字权值

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题