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...! but When constraints are large say 10^5 then we have to apply legendre's formula : )
Constraints are: n <= 10^6. And that complexity of that approch is: O(nlogn).