首页 > 试题广场 >

小苯的数字权值

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

热度指数：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

说明

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

算法知识视频讲解

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)