You are given a number A, convert A to number D by following steps.
Convert A to basic form B Basic form contains exactly single occurence of all prime factors of A. eg. if A=12 -> (2 x 2 x 3) then B = 2x3 = 6 if A=120, then B=2x3x5=30 After converting into basic number, then multiply all it's divisors to get a number C.
Count the number of divisors of C, you get your final answer which is D.
Find D and print is module 1e9+7
Constraints: 2<=A<=10^15
Sample input: 12 Sample output: 9
Explanation: A = 2 x 2 x 3 hence basic form B = 2 x 3 = 6
The divisors of B are 1, 2, 3, 4. Hence C = 1 x 2 x 3 x 6 = 36
The divisors of C are 1, 2, 3, 4, 6, 9, 12, 18, 36. Therefore the D or the count of divisors of C is 9
Sample Input: 71 Sample Output: 2
I calculated prime numbers and divisors in O(sqrt(N)) each but my soln only passed 5/10 test cases. How to solve this question?
Thanks in advance.
All you need to do is compute the number of prime divizors of $$$A$$$. Let this number be $$$K$$$. Then the answer is $$$(2^{K-1}+1)^K$$$.
The proof:
First let's say that $$$B=p_1*p_2*...*p_K$$$. Then in order to find $$$C$$$ we iterate through $$$B$$$'s divisors and multiply, giving us that $$$C=p_1^{2^{K-1}}*p_2^{2^{K-1}}*...*p_K^{2^{K-1}}$$$. This is because there are exactly $$$2^K$$$ divisors of $$$B$$$ and exactly half of them are multiples of $$$p_i$$$. A well known formula states that the number of divizors of a number $$$p_1^{e_1}*p_2^{e_2}*...*p_k^{e_k}$$$ is $$$(e_1+1)*(e_2+1)*...*(e_k+1)$$$, giving us the final formula.
Final complexity is $$$O(\sqrt A+\log K)$$$ from prime factorization and logarithmic exponentiation.