codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.