核心结论

设

$x=\prod_{i=1}^{m} q_i^{a_i}$

是 $x$ 的质因数分解，其中：

• $q_i$ 是 $x$ 的第 $i$ 个 不同质因子；
• $a_i$ 是 $q_i$ 在 $x$ 中的 指数（质数 $q_i$ 在分解中的幂次）；
• $m$ 是不同质因子的个数；
• $A=\max{a_1,a_2,\dots,a_m}$ 表示所有质因子的最大指数。

对于每一个 指数层 $\ell$（$\ell=1,2,\dots,A$） ，定义：

$r_ell = \#\{\, i \mid a_i \ge \ell \,\}$

即 第 $\ell$ 层的质数个数，或者说在指数至少为 $\ell$ 的质因子数量。

什么时候拆开（用分层法）？

• 当：

$\sum_{\ell=1}^{A} 2^{\,r_\ell}>\tau(x)$

时，拆分为各层的平方自由因子 得到的答案更优。

• 其中：

  • $tau(x) = \prod_{i=1}^m (a_i+1)$ 为 $x$ 的正因子个数。
  • $\sum_{\ell=1}^{A} 2^{r_\ell}$ 表示按层拆分后各因子的权值之和（每层的平方自由数的正因子个数为 $2^{r_\ell}$）。

• 经验规律：

  • 幂次较大或多质因子的幂次分布比较均匀时，更倾向于拆开；
  • 特别是 $x=p^t$ 且 $t \ge 2$ 时必然拆（因为 $2t > t+1$）。

什么时候不拆（直接整个乘积）？

• 当：

$\tau(x) \ge \sum_{\ell=1}^{A} 2^{r_\ell}$

时，直接使用 $x$ 整体不拆分更优，答案取 $tau(x)$。

• 经验规律：

  • 当幂次普遍很小（特别是 $a_i=1$ 这种平方自由数）且质因子多时，不拆分往往更优；
  • 如果 $x$ 是平方自由数（所有 $a_i=1$），则两种方法数值相等，拆与不拆都可以。

最优答案公式

其中：

• $tau(x) = \prod_{i=1}^{m} (a_i+1)$ 表示 $x$ 的正因子个数；
• 表示第 $\ell$ 层出现的质因子个数。

C++

#include <bits/stdc++.h>
using namespace std;
using u64 = unsigned long long;

// 试除分解：只返回各质因子的幂次
static vector<int> factor_exps(u64 n) {
	vector<int> exps;
	if (n % 2 == 0) {
		int c = 0;
		while (n % 2 == 0) { n /= 2; ++c; }
		exps.push_back(c);
	}
	for (u64 p = 3; p <= n / p; p += 2) {
		if (n % p == 0) {
			int c = 0;
			while (n % p == 0) { n /= p; ++c; }
			exps.push_back(c);
		}
	}
	if (n > 1) exps.push_back(1);
	return exps;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	if (!(cin >> T)) return 0;
	while (T--) {
		u64 x; cin >> x;
		if (x == 1) { cout << 0 << '\n'; continue; } // 若题面保证 x>=2，可删除
		vector<int> exps = factor_exps(x);

		// 计算 tau(x) = ∏(a_i+1)
		u64 tau = 1;
		for (int a : exps) tau *= (u64)(a + 1);

		// 计算分层和 ∑ 2^{r_ell}
		int A = 0;
		for (int a : exps) A = max(A, a);
		u64 layerSum = 0;
		for (int ell = 1; ell <= A; ++ell) {
			int r = 0;
			for (int a : exps) if (a >= ell) ++r;
			layerSum += (1ULL << r);
		}

		cout << max(tau, layerSum) << '\n';
	}
	return 0;
}

Python

import sys

def factor_exps(n: int):
	# 返回各质因子幂次
	exps = []
	if n % 2 == 0:
		c = 0
		while n % 2 == 0:
			n //= 2
			c += 1
		exps.append(c)
	p = 3
	while p * p <= n:
		if n % p == 0:
			c = 0
			while n % p == 0:
				n //= p
				c += 1
			exps.append(c)
		p += 2
	if n > 1:
		exps.append(1)
	return exps

def solve():
	data = sys.stdin.read().strip().split()
	if not data: return
	it = iter(data)
	T = int(next(it))
	for _ in range(T):
		x = int(next(it))
		if x == 1:
			print(0)
			continue
		exps = factor_exps(x)

		# tau(x)
		tau = 1
		for a in exps:
			tau *= (a + 1)

		# 分层和
		A = max(exps) if exps else 0
		layer_sum = 0
		for ell in range(1, A + 1):
			r = sum(1 for a in exps if a >= ell)
			layer_sum += (1 << r)

		print(max(tau, layer_sum))

if __name__ == "__main__":
	solve()

Java

import java.io.*;
import java.util.*;

public class Main {
	static ArrayList<Integer> factorExps(long n) {
		// 返回各质因子的幂次
		ArrayList<Integer> exps = new ArrayList<>();
		if (n % 2 == 0) {
			int c = 0;
			while (n % 2 == 0) { n /= 2; c++; }
			exps.add(c);
		}
		for (long p = 3; p <= n / p; p += 2) {
			if (n % p == 0) {
				int c = 0;
				while (n % p == 0) { n /= p; c++; }
				exps.add(c);
			}
		}
		if (n > 1) exps.add(1);
		return exps;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine().trim());
		StringBuilder sb = new StringBuilder();
		while (T-- > 0) {
			long x = Long.parseLong(br.readLine().trim());
			if (x == 1) { sb.append(0).append('\n'); continue; }
			ArrayList<Integer> exps = factorExps(x);

			// tau(x) = ∏(a_i+1)
			long tau = 1;
			for (int a : exps) tau *= (a + 1L);

			// 分层和 ∑ 2^{r_ell}
			int A = 0;
			for (int a : exps) A = Math.max(A, a);
			long layerSum = 0;
			for (int ell = 1; ell <= A; ++ell) {
				int r = 0;
				for (int a : exps) if (a >= ell) r++;
				layerSum += (1L << r);
			}
			sb.append(Math.max(tau, layerSum)).append('\n');
		}
		System.out.print(sb.toString());
	}
}

题目内容

定义正整数 $n$ 的权值为 $n$ 的正因子的数量，即 $wt(n)=r(n)$ ，

其中 $r(n)$ 表示 $n$ 的因子个数。

给定一个正整数 $x$ ，你可以将 $x$ 分解为若干个大于 $1$ 的正整数 $p_1,p_2,...,p(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$ 。