首页 > 试题广场 >

小苯的数字权值

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

热度指数：3540 时间限制：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

说明

 对于 ，无法再分解，只能取自身，。 
 对于 ，最优方案为 ，，总和 。 
 对于 ，最优方案为 ，，总和 。

算法知识视频讲解

Mag1c0nch

发表于 2024-11-25 20:00:08

假设表示质因子的数量，定义为一个数拆成其全部质因子的权值，定义为一个数不拆情况下的权值，也就是一个数的因子数量，一个数因子的数量是其每个质因子数量加一的乘积，如何证明？举个例，而 12 的因子其实就是在修改等式右边的指数，每个数的指数的取值范围是，指数为几就代表选择了几个展开全文

追赶时间a

发表于 2024-11-26 16:48:26

import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner scan 展开全文

Silencer76

发表于 2025-07-08 19:38:08

题目链接 HIGH7 小苯的数字权值题目描述给定一个正整数 x，你可以将其分解为 x = y_1 * y_2 * ... * y_k，其中 y_i > 1。我们定义一个数 n 的权值为其约数的个数，记作 wt(n)。请你找到一种分解方案，使得权值之和 wt(y_1) + wt(y_2) 展开全文

missay情玖

发表于 2024-11-26 16:51:18

#include <iostream> #include <vector> # include<bits/stdc++.h> using namespace std; const int MAX = 200010; // 最大值 2 * 10^5 int a 展开全文

希望奇迹发生的小黄鸭很不想泡池子

发表于 2025-06-10 11:40:07

这个问题涉及到数字的权值计算，其中权值定义为数字的正因子个数。我们需要比较将数字拆分成质因数与不拆分时的权值和。 ### 情况1：质因数只有一种以 $8 = 2^3$ 为例： - **不拆分**：8 的因子有 1, 2, 4, 8，共 4 个，所以权值和为 4。 - **拆分**：将 8 拆展开全文

Kato_Shoko

发表于 2024-11-26 18:18:00

#include <iostream> #include <queue> #include <map> #include <set> #include <cmath> #include <cstring> #include &l 展开全文

ylh123_

发表于 2025-12-09 20:12:19

刚开始以为无脑拆就行了后来发现70这个数字就不是这样虽然可能有更简单的解时间复杂度更优（不知道有没有但感觉应该是有的）但是我这里有一种不要脑子的做法，只需要会简单的dp和调和级数预处理因子就行预处理时间复杂度O(NlogN),查询O(1),空间复杂度O(NlogN)，其中N是2e5 #include 展开全文

八重嘤嘤嘤嘤嘤嘤嘤嘤

发表于 2024-11-27 12:48:15

把数字拆成质因数 x 后，x 的权值为 2。在质因数只有一种的时候，例如 8 = 2 * 2 * 2，如果不拆的话可以得到的权值和为 4（1，2，4，8）。如果拆开的话可以拆成 3个2，权值和为3 * 2。在质因数有多种时，例如70 = 2 * 5 * 7，不拆的话可以得到的权值和为 8（1，2 展开全文