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, In English

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

 
 
 
 
  • Vote: I like it
  • +88
  • Vote: I do not like it

»
19 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes...! but When constraints are large say 10^5 then we have to apply legendre's formula : )

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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