1787B.md (1717B)
1 Source: https://codeforces.com/problemset/problem/1787/B 2 3 B. Number Factorization 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Given an integer $n$. 22 23 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 \gt 1;p_i \gt 0$) and $a_i$ is the product of some (possibly one) distinct prime numbers. 24 25 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. 26 27 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. 28 29 Input 30 31 Each test contains multiple test cases. The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases. 32 33 Each test case contains only one integer $n$ ($2 \le n \le 10^9$). 34 35 Output 36 37 For each test case, print the maximum value of $\sum a_i \cdot p_i$. 38 39 Example 40 41 Input 42 43 ``` 44 7 45 46 100 47 48 10 49 50 864 51 52 130056192 53 54 1000000000 55 56 2 57 58 999999018 59 ``` 60 61 Output 62 63 ``` 64 20 65 10 66 22 67 118 68 90 69 2 70 333333009 71 ``` 72 73 Note 74 75 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. 76 77 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$.