Rajib_119's blog

Pairs Forming LCM
By Rajib_119, history, 7 years ago, In English

Anyone please elaborate the problem. Thanks in Advance.

  • Vote: I like it
  • -6
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

Let's solve the problem for each prime factor p separately.

Suppose LCM of two numbers i and j has pe in its factorization, then at least one of them must have pe in its factorization as well. There are (e + 1)2 - e2 ways to choose the exponents of p so that one of the numbers has exponent e and the other one has exponent at most e.

First let's make a list of primes with a sieve, then solve the problem for each prime factor as explained above. The results have to be multiplied because each prime factor is independent.

We'll be counting all pairs twice, except the case when i = j (when n is a perfect square), so if the answer calculated is res then will do the trick.

→ Reply