Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### Vivek.p's blog

By Vivek.p, history, 19 months ago,

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$.

1. 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.
2. 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!$.

• +88

 » 19 months ago, # | ← Rev. 2 →   +1 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)
•  » » 19 months ago, # ^ |   0 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.
•  » » 15 months ago, # ^ |   0 yes...! but When constraints are large say 10^5 then we have to apply legendre's formula : )
•  » » » 15 months ago, # ^ |   0 Constraints are: n <= 10^6. And that complexity of that approch is: O(nlogn).