CF1787B 题解

ikunTLE · 2024-08-02 12:07:46 · 题解

题目传送门

题目大意

给出一个正整数 n，将 n 分解成其质因数不能重复的因数的幂的乘积，使因数与它们的幂指数的乘积之和最大。

思路

将 n 分解质因数，存储在序列 A，每一次从剩下的质因子里各取一个数相乘得到新的数，并将其加和。

举例说明：864=2^5\times3^3，那么 A=\{2,2,2,2,2,3,3,3\}。前三次需将所有的质因子全部相乘，即各取一个 2 和一个 3，第四次取两个 2，最终答案为 6\times3+2\times2=22。同理，130056192=2^{15}\times3^4\times7^2=42^2\times6^2\times2^{11}，答案为 42\times2+6\times2+2\times11=118。