Powerful Number

adnan_toky Criterion 2022 Round 16

The number xyx^y is powerful. Let the prime factorization of xx be p1e1×p2e2×p3e3××pkekp_1^{e_1} \times p_2^{e_2} \times p_3^{e_3}\times … \times p_k^{e_k}, then the prime factorization of xyx^y will be p1y.e1×p2y.e2×p3y.e3×...×pky.ekp_1^{y.e_1}\times p_2^{y.e_2} \times p_3^{y.e_3} \times ... \times p_k^{y.e_k}. So the power of each prime of xyx^y is a multiple of yy.

Let the prime factorization of nn be p1e1×p2e2×p3e3××pkekp_1^{e_1} \times p_2^{e_2} \times p_3^{e_3} \times … \times p_k^{e_k} and the maximum among e1,e2,e3,,eke_1, e_2, e_3, …, e_k be ee. If y>ey > e, then xyx^y must be greater than or equal to n2n^2. As we know, n2n^2 is a powerful number, nn is a probable value of pp and we don’t need to care about the values greater than n2n^2. There may exist some smaller value than n2n^2 which is powerful. To find them, we can iterate from 22 to ee and for each 2ie2 \leq i \leq e, we want to find the minimum value pip_i required to make nn in the form xix^i. The number n×pin\times p_i is in the form xix^i iff the power of each prime divisor of nn is a multiple of ii. So, for each ii, we can multiply each prime the minimum number of times such that the power of that prime is a multiple of ii. The answer is the minimum among all such pip_i.

The only exception is when nn is 11. In this case, the answer is 44. Time complexity is O(k)O(k) for each test case where kk is the total number of primes less than n\sqrt{n}.


42% Solution Ratio
NirjhorEarliest, 3M ago
arnab_1810043Fastest, 0.0s
anisur_rahmanLightest, 131 kB
jewel.samaShortest, 987B
Toph uses cookies. By continuing you agree to our Cookie Policy.