310132: CF1787B. Number Factorization
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Number Factorization
题意翻译
给定一个整数 $n$。 考虑所有长度相同的整数数组对 $a$ 和 $p$ ，使得 $n=\prod a_i^{p_i} (a_1^{p_1}\times a^{p_2}_2\times...)$($a_i>1$；$p_i>0$)，$a_i$ 是一些（可能是一个）不同素数的乘积。 对于所有可能的整数数组对 $a$ 和 $p$，找到 $\sum_{i=1} a_i\times p_i$ 的最大值。（$a_1\times p_1+a_2\times p_2+...$） 第一行输入整数 $t$（$1≤t≤1000$)，表示有 $t$ 组测试用例。 接下来 $t$ 行，输入一个整数 $n$（$2≤n≤10^9$）。 对于每组数据，输出 $\sum_{i=1} a_i\times p_i$的最大值。题目描述
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 $ .
输入输出样例
输入样例 #1
7
100
10
864
130056192
1000000000
2
999999018输出样例 #1
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 $ .Input
题意翻译
给定一个整数 $n$。 考虑所有长度相同的整数数组对 $a$ 和 $p$ ，使得 $n=\prod a_i^{p_i} (a_1^{p_1}\times a^{p_2}_2\times...)$($a_i>1$；$p_i>0$)，$a_i$ 是一些（可能是一个）不同素数的乘积。 对于所有可能的整数数组对 $a$ 和 $p$，找到 $\sum_{i=1} a_i\times p_i$ 的最大值。（$a_1\times p_1+a_2\times p_2+...$） 第一行输入整数 $t$（$1≤t≤1000$)，表示有 $t$ 组测试用例。 接下来 $t$ 行，输入一个整数 $n$（$2≤n≤10^9$）。 对于每组数据，输出 $\sum_{i=1} a_i\times p_i$的最大值。Output
**数因式分解**
**题意翻译**
给定一个整数 \( n \)。
考虑所有长度相同的整数数组对 \( a \) 和 \( p \)，使得 \( n = \prod a_i^{p_i} \) (\( a_1^{p_1} \times a_2^{p_2} \times ... \)) (\( a_i > 1 \)；\( p_i > 0 \))，\( a_i \) 是一些（可能是一个）不同素数的乘积。
对于所有可能的整数数组对 \( a \) 和 \( p \)，找到 \( \sum_{i=1} a_i \times p_i \) 的最大值。（\( a_1 \times p_1 + a_2 \times p_2 + ... \)）
第一行输入整数 \( t \)（\( 1 \leq t \leq 1000 \)），表示有 \( t \) 组测试用例。
接下来 \( t \) 行，输入一个整数 \( n \)（\( 2 \leq n \leq 10^9 \)）。
对于每组数据，输出 \( \sum_{i=1} a_i \times p_i \) 的最大值。
**题目描述**
给定一个整数 \( n \)。
考虑所有相同长度的整数数组对 \( a \) 和 \( p \)，使得 \( n = \prod a_i^{p_i} \)（即 \( a_1^{p_1} \cdot a_2^{p_2} \cdot \ldots \)）(\( a_i > 1; p_i > 0 \)) 且 \( a_i \) 是一些（可能是一个）不同素数的乘积。
例如，对于 \( n = 28 = 2^2 \cdot 7^1 = 4^1 \cdot 7^1 \)，数组对 \( a = [2, 7] \), \( p = [2, 1] \) 是正确的，但是数组对 \( a = [4, 7] \), \( p = [1, 1] \) 是不正确的，因为 \( 4 = 2^2 \) 是非不同素数的乘积。
你的任务是找到所有可能的数组对 \( a \) 和 \( p \) 的 \( \sum a_i \cdot p_i \) 的最大值（即 \( a_1 \cdot p_1 + a_2 \cdot p_2 + \ldots \)）。注意，你不需要最小化或最大化数组的长度。
**输入输出格式**
**输入格式**
每个测试包含多个测试用例。第一行包含一个整数 \( t \) (\( 1 \leq t \leq 1000 \)）——测试用例的数量。
每个测试用例只包含一个整数 \( n \) (\( 2 \leq n \leq 10^9 \))。
**输出格式**
对于每个测试用例，打印 \( \sum a_i \cdot p_i \) 的最大值。
**输入输出样例**
**输入样例 #1**
```
7
100
10
864
130056192
1000000000
2
999999018
```
**输出样例 #1**
```
20
10
22
118
90
2
333333009
```
**说明**
在第一个测试用例中，\( 100 = 10^2 \)，使得 \( a = [10] \), \( p = [2] \) 时 \( \sum a_i \cdot p_i \) 达到最大值 \( 10 \cdot 2 = 20 \)。同时，\( a = [100] \), \( p = [1] \) 不成立，因为 \( 100 \) 不是由不同素因子组成的。
在第二个测试用例中，我们可以将 \( 10 \) 视为 \( 10^1 \)，所以 \( a = [10] \), \( p = [1] \)。注意，当 \( 10 = 2^1 \cdot 5^1 \)，\( \sum a_i \cdot p_i = 7 \)。**数因式分解** **题意翻译** 给定一个整数 \( n \)。 考虑所有长度相同的整数数组对 \( a \) 和 \( p \)，使得 \( n = \prod a_i^{p_i} \) (\( a_1^{p_1} \times a_2^{p_2} \times ... \)) (\( a_i > 1 \)；\( p_i > 0 \))，\( a_i \) 是一些（可能是一个）不同素数的乘积。 对于所有可能的整数数组对 \( a \) 和 \( p \)，找到 \( \sum_{i=1} a_i \times p_i \) 的最大值。（\( a_1 \times p_1 + a_2 \times p_2 + ... \)） 第一行输入整数 \( t \)（\( 1 \leq t \leq 1000 \)），表示有 \( t \) 组测试用例。 接下来 \( t \) 行，输入一个整数 \( n \)（\( 2 \leq n \leq 10^9 \)）。 对于每组数据，输出 \( \sum_{i=1} a_i \times p_i \) 的最大值。 **题目描述** 给定一个整数 \( n \)。 考虑所有相同长度的整数数组对 \( a \) 和 \( p \)，使得 \( n = \prod a_i^{p_i} \)（即 \( a_1^{p_1} \cdot a_2^{p_2} \cdot \ldots \)）(\( a_i > 1; p_i > 0 \)) 且 \( a_i \) 是一些（可能是一个）不同素数的乘积。 例如，对于 \( n = 28 = 2^2 \cdot 7^1 = 4^1 \cdot 7^1 \)，数组对 \( a = [2, 7] \), \( p = [2, 1] \) 是正确的，但是数组对 \( a = [4, 7] \), \( p = [1, 1] \) 是不正确的，因为 \( 4 = 2^2 \) 是非不同素数的乘积。 你的任务是找到所有可能的数组对 \( a \) 和 \( p \) 的 \( \sum a_i \cdot p_i \) 的最大值（即 \( a_1 \cdot p_1 + a_2 \cdot p_2 + \ldots \)）。注意，你不需要最小化或最大化数组的长度。 **输入输出格式** **输入格式** 每个测试包含多个测试用例。第一行包含一个整数 \( t \) (\( 1 \leq t \leq 1000 \)）——测试用例的数量。 每个测试用例只包含一个整数 \( n \) (\( 2 \leq n \leq 10^9 \))。 **输出格式** 对于每个测试用例，打印 \( \sum a_i \cdot p_i \) 的最大值。 **输入输出样例** **输入样例 #1** ``` 7 100 10 864 130056192 1000000000 2 999999018 ``` **输出样例 #1** ``` 20 10 22 118 90 2 333333009 ``` **说明** 在第一个测试用例中，\( 100 = 10^2 \)，使得 \( a = [10] \), \( p = [2] \) 时 \( \sum a_i \cdot p_i \) 达到最大值 \( 10 \cdot 2 = 20 \)。同时，\( a = [100] \), \( p = [1] \) 不成立，因为 \( 100 \) 不是由不同素因子组成的。 在第二个测试用例中，我们可以将 \( 10 \) 视为 \( 10^1 \)，所以 \( a = [10] \), \( p = [1] \)。注意，当 \( 10 = 2^1 \cdot 5^1 \)，\( \sum a_i \cdot p_i = 7 \)。
**题意翻译**
给定一个整数 \( n \)。
考虑所有长度相同的整数数组对 \( a \) 和 \( p \)，使得 \( n = \prod a_i^{p_i} \) (\( a_1^{p_1} \times a_2^{p_2} \times ... \)) (\( a_i > 1 \)；\( p_i > 0 \))，\( a_i \) 是一些（可能是一个）不同素数的乘积。
对于所有可能的整数数组对 \( a \) 和 \( p \)，找到 \( \sum_{i=1} a_i \times p_i \) 的最大值。（\( a_1 \times p_1 + a_2 \times p_2 + ... \)）
第一行输入整数 \( t \)（\( 1 \leq t \leq 1000 \)），表示有 \( t \) 组测试用例。
接下来 \( t \) 行，输入一个整数 \( n \)（\( 2 \leq n \leq 10^9 \)）。
对于每组数据，输出 \( \sum_{i=1} a_i \times p_i \) 的最大值。
**题目描述**
给定一个整数 \( n \)。
考虑所有相同长度的整数数组对 \( a \) 和 \( p \)，使得 \( n = \prod a_i^{p_i} \)（即 \( a_1^{p_1} \cdot a_2^{p_2} \cdot \ldots \)）(\( a_i > 1; p_i > 0 \)) 且 \( a_i \) 是一些（可能是一个）不同素数的乘积。
例如，对于 \( n = 28 = 2^2 \cdot 7^1 = 4^1 \cdot 7^1 \)，数组对 \( a = [2, 7] \), \( p = [2, 1] \) 是正确的，但是数组对 \( a = [4, 7] \), \( p = [1, 1] \) 是不正确的，因为 \( 4 = 2^2 \) 是非不同素数的乘积。
你的任务是找到所有可能的数组对 \( a \) 和 \( p \) 的 \( \sum a_i \cdot p_i \) 的最大值（即 \( a_1 \cdot p_1 + a_2 \cdot p_2 + \ldots \)）。注意，你不需要最小化或最大化数组的长度。
**输入输出格式**
**输入格式**
每个测试包含多个测试用例。第一行包含一个整数 \( t \) (\( 1 \leq t \leq 1000 \)）——测试用例的数量。
每个测试用例只包含一个整数 \( n \) (\( 2 \leq n \leq 10^9 \))。
**输出格式**
对于每个测试用例，打印 \( \sum a_i \cdot p_i \) 的最大值。
**输入输出样例**
**输入样例 #1**
```
7
100
10
864
130056192
1000000000
2
999999018
```
**输出样例 #1**
```
20
10
22
118
90
2
333333009
```
**说明**
在第一个测试用例中，\( 100 = 10^2 \)，使得 \( a = [10] \), \( p = [2] \) 时 \( \sum a_i \cdot p_i \) 达到最大值 \( 10 \cdot 2 = 20 \)。同时，\( a = [100] \), \( p = [1] \) 不成立，因为 \( 100 \) 不是由不同素因子组成的。
在第二个测试用例中，我们可以将 \( 10 \) 视为 \( 10^1 \)，所以 \( a = [10] \), \( p = [1] \)。注意，当 \( 10 = 2^1 \cdot 5^1 \)，\( \sum a_i \cdot p_i = 7 \)。**数因式分解** **题意翻译** 给定一个整数 \( n \)。 考虑所有长度相同的整数数组对 \( a \) 和 \( p \)，使得 \( n = \prod a_i^{p_i} \) (\( a_1^{p_1} \times a_2^{p_2} \times ... \)) (\( a_i > 1 \)；\( p_i > 0 \))，\( a_i \) 是一些（可能是一个）不同素数的乘积。 对于所有可能的整数数组对 \( a \) 和 \( p \)，找到 \( \sum_{i=1} a_i \times p_i \) 的最大值。（\( a_1 \times p_1 + a_2 \times p_2 + ... \)） 第一行输入整数 \( t \)（\( 1 \leq t \leq 1000 \)），表示有 \( t \) 组测试用例。 接下来 \( t \) 行，输入一个整数 \( n \)（\( 2 \leq n \leq 10^9 \)）。 对于每组数据，输出 \( \sum_{i=1} a_i \times p_i \) 的最大值。 **题目描述** 给定一个整数 \( n \)。 考虑所有相同长度的整数数组对 \( a \) 和 \( p \)，使得 \( n = \prod a_i^{p_i} \)（即 \( a_1^{p_1} \cdot a_2^{p_2} \cdot \ldots \)）(\( a_i > 1; p_i > 0 \)) 且 \( a_i \) 是一些（可能是一个）不同素数的乘积。 例如，对于 \( n = 28 = 2^2 \cdot 7^1 = 4^1 \cdot 7^1 \)，数组对 \( a = [2, 7] \), \( p = [2, 1] \) 是正确的，但是数组对 \( a = [4, 7] \), \( p = [1, 1] \) 是不正确的，因为 \( 4 = 2^2 \) 是非不同素数的乘积。 你的任务是找到所有可能的数组对 \( a \) 和 \( p \) 的 \( \sum a_i \cdot p_i \) 的最大值（即 \( a_1 \cdot p_1 + a_2 \cdot p_2 + \ldots \)）。注意，你不需要最小化或最大化数组的长度。 **输入输出格式** **输入格式** 每个测试包含多个测试用例。第一行包含一个整数 \( t \) (\( 1 \leq t \leq 1000 \)）——测试用例的数量。 每个测试用例只包含一个整数 \( n \) (\( 2 \leq n \leq 10^9 \))。 **输出格式** 对于每个测试用例，打印 \( \sum a_i \cdot p_i \) 的最大值。 **输入输出样例** **输入样例 #1** ``` 7 100 10 864 130056192 1000000000 2 999999018 ``` **输出样例 #1** ``` 20 10 22 118 90 2 333333009 ``` **说明** 在第一个测试用例中，\( 100 = 10^2 \)，使得 \( a = [10] \), \( p = [2] \) 时 \( \sum a_i \cdot p_i \) 达到最大值 \( 10 \cdot 2 = 20 \)。同时，\( a = [100] \), \( p = [1] \) 不成立，因为 \( 100 \) 不是由不同素因子组成的。 在第二个测试用例中，我们可以将 \( 10 \) 视为 \( 10^1 \)，所以 \( a = [10] \), \( p = [1] \)。注意，当 \( 10 = 2^1 \cdot 5^1 \)，\( \sum a_i \cdot p_i = 7 \)。