Number Factorization

题目链接

题目描述：

Given an integer \(n\).

Consider all pairs of integer arrays \(a\) and \(p\) of the same length such that \(n=∏a^{pi}_i\)\((\)i.e. \(a^{p1}_1⋅a^{p2}_2⋅…) (a_i>1;p_i>0)\) and ai is the product of some (possibly one) distinct prime numbers.

For example, for \(n=28=2^2⋅7^1=4^1⋅7^1\) the array pair \(a=[2,7], p=[2,1]\) is correct, but the pair of arrays \(a=[4,7], p=[1,1]\) is not, because \(4=2^2\) is a product of non-distinct prime numbers.

Your task is to find the maximum value of \(∑a_i⋅p_i\) \((\)i.e. \(a_1⋅p_1+a_2⋅p_2+…)\) over all possible pairs of arrays \(a\) and \(p\).

Note that you do not need to minimize or maximize the length of the arrays.

输入描述：

Each test contains multiple test cases. The first line contains an integer \(t(1≤t≤1000 )\) — the number of test cases.

Each test case contains only one integer \(n(2≤n≤10^9)\).

输出描述：

For each test case, print the maximum value of \(∑a_i⋅p_i\).

样例：

input:

7
100
10
864
130056192
1000000000
2
999999018

output:

20
10
22
118
90
2
333333009

Note:

In the first test case, \(100=10^2\) so that \(a=[10]\), \(p=[2]\) when \(∑a_i⋅p_i\) hits the maximum value \(10⋅2=20\). Also, \(a=[100]\), \(p=[1]\) does not work since \(100\) is not made of distinct prime factors.

In the second test case, we can consider \(10\) as \(10^1\), so \(a=[10]\), \(p=[1]\). Notice that when \(10=2^1⋅5^1\), \(∑a_i⋅p_i=7\).

AC代码：

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

PII p[N];
int d[N];

// 根据题意可得要找到多个不同质数的乘积和它的幂
// 可以先用试除法求出质因子和它的幂
// 随后根据幂从小到大排序
// 从大到小遍历一边，将所有质因子的可能出现的乘积求出来
// 最后再从小到大遍历一边，用当前数的幂减去前一个数的幂即为当前质数乘积之和的幂
void solve()
{
	int n;
	cin >> n;

	int cnt = 0;

	// 试除法求质因子和幂
	for(int i = 2; i <= n / i; i ++)
	{
		if(n % i == 0)
		{
			int m = 0;
			while(n % i == 0)
			{
				m ++;

				n /= i;
			}
			
			p[++ cnt] = {m, i};
		}
	}

	if(n > 1)
		p[++ cnt] = {1, n};

	sort(p + 1, p + 1 + cnt);

	d[cnt + 1] = 1;

	int ans = 0;

	// 因为幂小的数会最先被用完，所以从大到小求出质数乘积
	for(int i = cnt; i >= 1; i --)
		d[i] = d[i + 1] * p[i].second;
	

	for(int i = 1; i <= cnt; i ++)
		// 减去前面已经被用过的次数，就是当前乘积的幂
		if(p[i].first != p[i - 1].first)
			ans += d[i] * (p[i].first - p[i - 1].first);
		

	cout << ans << '\n';
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

	int T;
	cin >> T;

	while(T --)
		solve();

	return 0;
}