Official

B - Product of Divisors Editorial by evima


By prime factorizing \(A\), we can express it as follows:

\(A=\prod_{i}^{n} p_{i}^{e_{i}}.\)

Here, \(p_{1},p_{2},\dots p_{n}\) are distinct prime numbers, and \(e_{1},e_{2},\dots e_{n}\) are positive integers greater than or equal to \(1\).

An integer \(A\) that can be expressed in this form has exactly \(\prod_{i}^{n}(e_{i}+1)\) positive divisors.

From \(A^{B}=\prod_{i}^{n} p_{i}^{e_{i}B}\), the number of positive divisors of \(A^{B}\) is \(\prod_{i}^{n}(e_{i}B+1)\).

Also, for any positive integer \(X\), the geometric mean of the positive divisors of \(X\) is \(\sqrt{X}\) (because the mapping \(f:S\rightarrow S ;f(a)=\frac{X}{a}\) is a bijection, where \(S\) is the set of positive divisors of \(X\)).

Thus, the total product of the positive divisors of \(A^{B}\) is \((A^{\frac{B}{2}})^{\prod_{i}^{n}(e_{i}B+1)}\).

Therefore, the value to be found is the integer part of \(\frac{B\prod_{i}^{n}(e_{i}B+1)}{2}\).

Although the above value is an integer in many cases, note that the numerator will be odd if \(B\) is odd and \(A\) is a perfect square.

The computational complexity is \(O(\sqrt{A})\).

posted:
last update: