PROBLEM LINK:
Author: Bhushan Khanale
Editorialist: Bhushan Khanale
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Number Theory.
PROBLEM:
Prime factors of a number, say A, are provided. Now, a number K is formed by the product of all divisors of A. The problem is to find the total number of divisors of K mod 10^9+7.
QUICK EXPLANATION:
It is known that the number of divisors of n=\prod p_i^{\alpha_i} equals \prod (\alpha_i + 1) where p_i are primes in the factorization of n. Using this basic concept we can easily solve this problem.
EXPLANATION:
Lets define P as the product of all divisors of n. If we find \beta_i where P=\prod p_i^{\beta_i} we can solve the problem.
All divisors of n=\prod p_i^{\alpha_i} can be represented as d = \prod p_i^{k_i} where 0 \leq k_i \leq \alpha_i.
Lets fix some i_0 and 0 \leq k_0 \leq \alpha_i. There are \prod_{i \neq i_0}(\alpha_i + 1) divisors that k_{i_0}=k_0.
So \beta_i = (0 + 1 + ... + \alpha_i) \cdot \prod_{i \neq i_0}(\alpha_i + 1) = \frac{\alpha_i (\alpha_i + 1)}{2} \cdot \prod_{i \neq i_0}(\alpha_i + 1) = \frac{\alpha_i (\alpha_i + 1)}{2} \cdot \frac {allProd}{\alpha_i + 1} = \frac{\alpha_i}{2} \cdot allProd, where allProd = \prod(\alpha_i + 1).
Hence we can calculate the number of divisors using \beta_i.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.