Recently, i was solving some mathematical problems from the Hackerrank math's section, And i came up with this formula :

$$$\dfrac{1}{x}+\dfrac{1}{y}=\dfrac{1}{n!}$$$

The question was find the number of positive integral solutions for $$$\dfrac{1}{x}+\dfrac{1}{y}=\dfrac{1}{n!}$$$ equation. You can find the problem here.

#### My solution :

$$$\dfrac{1}{x}+\dfrac{1}{y}=\dfrac{1}{n!}$$$ , Consider N = n!.

Now,the equation,

**$$$\dfrac{1}{x}+\dfrac{1}{y}=\dfrac{1}{N}$$$**

∴ $$$\dfrac{x+y}{xy} = \dfrac{1}{N}$$$

∴ $$$N( {x + y} ) = xy$$$

∴ $$${xy - N({x+y})} = 0$$$

Now adding both sides with N^2 :

$$${xy - N( {x + y}) + N^2} = N^2$$$

∴ $$${xy - Nx - Ny + N^2} = N^2$$$

∴ $$${x({y - N}) - N ({y - N })} = N^2$$$

**∴ $$$({x - N}) ({y - N}) = N^2$$$**

From this equation we know that number solution will be the number of divisiors of N.

That means we only need to find number of divisors of **$$$n!^2$$$**.

- Now one way is find value of $$$n!^2$$$ and find the number of divisors of them.But for less time complexity we can find number of divisiors $$$n!^2$$$ by Legendre's formula.
For that,

- Find all prime numbers less than equals to $$$n$$$.Let say prime numbers less than equals to $$$n$$$ : [p,p1,p2,...]
- For each prime number p find the largest power of it that divides $$$n!$$$. We use below Legendre's formula for this purpose.

The value of largest power that divides p is $$$⌊n/p⌋ + ⌊n/(p1)⌋ + ⌊n/(p2)⌋ + ...$$$

- Let these largest powers are : [e,e1,e2,...]
- So, for number of divisors of $$$n!$$$ the result is $$${({e + 1}) * ({e1 + 1}) * ({e2 + 1}) ...}$$$ .
- And for $$$n!^2$$$ the result will be : $$${({2*e + 1}) * ({2*e1 + 1}) * ({2*e2 + 1}) ...}$$$.

And that is the **answer** we are looking for.

For example, lets take $$$n=4$$$, $$$n! = 24$$$ and $$$(n!)^2 = 576$$$.

$$$24 = 2^3 * 3^1$$$

Hence no. of factors $$$= (3+1) * (1+1) = 8$$$, which are : [1,2,3,4,6,8,12,24].

For $$$576 = 2^6 * 3^2$$$,

it is $$$(2*3 + 1) * (2*1 + 1) = 21$$$;

Hence for $$$\dfrac{1}{x}+\dfrac{1}{y}=\dfrac{1}{4!}$$$ this equation total number of positive integral solution are $$$21$$$.

So, that was my answer for the question,Correct me if i am wrong.

Here is more information about finding divisors of $$$n!$$$.

I think, it should be better if you use sieve and find factorization of 2 ... n(factorization of n!).and then find total divisors of number.which should be better in terms of complexity ? i don't have any idea !! can anyone tell me ?Edit : My Solution(AC)Yes, if we use sieve's algorithm to find prime numbers it will do the work in $$$nlogn$$$ time complexity.And will reduce the overall time complexity.

yes...! but When constraints are large say 10^5 then we have to apply

legendre'sformula : )Constraints are: n <= 10^6. And that complexity of that approch is: O(nlogn).