解题思路

题意： 定义正整数 $n$ 的权值为其正因子的数量，即

其中 $\tau(n)$ 表示 $n$ 的正因子个数。

给定一个整数 $x$，你可以把它拆成若干个大于 1 的整数 $p_1, p_2, ..., p_k$，要求：

• $p_1 \times p_2 \times \cdots \times p_k = x$
• 最大化 $\sum wt(p_i)$

核心思路：

1. 性质分析：

   • 对于质数 $p$，$\tau(p)=2$。
   • 对于合数，若 $n=a\times b$，则 $\tau(n)=\tau(a)\tau(b)$。
   • 由于权值定义与因子分解相关，我们希望把 $x$ 拆分成若干部分，使得每部分的 $\tau(p_i)$ 之和最大。

2. 动态规划： 定义 dp[x] 表示整数 x 的最大权值和。 转移方程：

   $dp[x]$ = $\max(\tau(x), \max_{d|x, 1<d<x} (dp[d] + dp[x/d]))$

   即：

   • 不拆时取自身权值；
   • 拆分时取所有因数组合的最大值。

3. 优化计算：

   • 先预处理每个数的因子数 tau；
   • 然后依次递推所有 dp[x]；
   • 由于 x ≤ 2*10^5，复杂度可接受。

复杂度分析

• 时间复杂度： 预处理因子数 O(n log n)， 动态规划拆分时每个数约遍历其因数 O(n log n)，总体 O(n log n)。

• 空间复杂度： O(n)，用于存储 tau 与 dp 数组。

代码实现

Python

# 计算权值最大化
def solve():
    import sys
    input = sys.stdin.readline

    MAXN = 200000
    tau = [0] * (MAXN + 1)
    # 预处理每个数的因子个数
    for i in range(1, MAXN + 1):
        for j in range(i, MAXN + 1, i):
            tau[j] += 1

    dp = [0] * (MAXN + 1)
    for i in range(2, MAXN + 1):
        dp[i] = tau[i]
        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])

if __name__ == "__main__":
    solve()

Java

import java.util.*;

public class Main {
    static int MAXN = 200000;
    static int[] tau = new int[MAXN + 1];
    static int[] dp = new int[MAXN + 1];

    // 主函数
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 预处理每个数的因子个数
        for (int i = 1; i <= MAXN; i++) {
            for (int j = i; j <= MAXN; j += i) {
                tau[j]++;
            }
        }

        // 动态规划计算最大权值
        for (int i = 2; i <= MAXN; i++) {
            dp[i] = tau[i];
            for (int j = 2; j * j <= i; j++) {
                if (i % j == 0) {
                    dp[i] = Math.max(dp[i], dp[j] + dp[i / j]);
                }
            }
        }

        int T = sc.nextInt();
        while (T-- > 0) {
            int x = sc.nextInt();
            System.out.println(dp[x]);
        }
        sc.close();
    }
}

C++

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

const int MAXN = 200000;
int tauArr[MAXN + 1];
int dp[MAXN + 1];

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

    // 预处理每个数的因子个数
    for (int i = 1; i <= MAXN; i++) {
        for (int j = i; j <= MAXN; j += i)
            tauArr[j]++;
    }

    // 动态规划计算最大权值
    for (int i = 2; i <= MAXN; i++) {
        dp[i] = tauArr[i];
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0)
                dp[i] = max(dp[i], dp[j] + dp[i / j]);
        }
    }

    int T; cin >> T;
    while (T--) {
        int x; cin >> x;
        cout << dp[x] << "\n";
    }
    return 0;
}

题目内容

定义正整数 $n$ 的权值为 $n$ 的正因子的数量，即 $wt(n)=\tau(n)$ ，其中 $\tau(n)$ 表示 $n$ 的因子个数。

给定一个正整数 $x$ ，你可以将 $x$ 分解为若干个大于 $1$ 的正整数 $p_1,p_2,…,p_n(k≥1)$ ，要求

• $p_1×p_2×...×p_k=x$;

• 最大化 $\sum^k_{i=1} wt(p_i)$ 。

请你求出在最优分解下，上述表达式的最大可能值。

输入描述

第一行输入一个整数 $T(1≦T≦10^4)$ 表示测试数据组数。

此后 $T$ 行，每行输入一个整数 $x(2≦x≦2×10^5)$ 。

输出描述

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

样例1

输入

3
2
10
123

输出

2
4
4

说明

对于 $x=2$，无法再分解，只能取自身，$wt(2) = 2$.

对于 $x=10$，最优方案为 $10=2×5,wt(2)= 2,wt(5)=2$,总和 $2+2=4$ .

对于 $x=123$，最优方案为 $123=3×41, wt(3) = 2,wt(41)=2$ ,总和 $4$ .