CHEFDI - Editorial

PROBLEM LINK:

Practice
Contest

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.