Preparando MOJI
Given an integer $$$n$$$.
Consider all pairs of integer arrays $$$a$$$ and $$$p$$$ of the same length such that $$$n = \prod a_i^{p_i}$$$ (i.e. $$$a_1^{p_1}\cdot a_2^{p_2}\cdot\ldots$$$) ($$$a_i>1;p_i>0$$$) and $$$a_i$$$ is the product of some (possibly one) distinct prime numbers.
For example, for $$$n = 28 = 2^2\cdot 7^1 = 4^1 \cdot 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 $$$\sum a_i \cdot p_i$$$ (i.e. $$$a_1\cdot p_1 + a_2\cdot p_2 + \ldots$$$) 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 \le t \le 1000$$$) — the number of test cases.
Each test case contains only one integer $$$n$$$ ($$$2 \le n \le 10^9$$$).
For each test case, print the maximum value of $$$\sum a_i \cdot p_i$$$.
71001086413005619210000000002999999018
20 10 22 118 90 2 333333009
In the first test case, $$$100 = 10^2$$$ so that $$$a = [10]$$$, $$$p = [2]$$$ when $$$\sum a_i \cdot p_i$$$ hits the maximum value $$$10\cdot 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\cdot 5^1$$$, $$$\sum a_i \cdot p_i = 7$$$.
Informação
Provedor Codeforces
Código CF1787B
Tags
Submetido 0
BOUA! 0
Taxa de BOUA's 0%
Datas 09/05/2023 10:36:25
Relacionados