sumit93's blog

Number theory
By sumit93, 12 years ago, In English

Given two number N,M.Count the number of pair(i,j) such that LCM(i,j)=i*j.Here M,N<=10^9 and min(M,N)=10^6. How can I do this?

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

»
12 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

lcm(i, j) = i * j, when gcd(i, j) = 1.

so problem is -> how many pairs (i, j) such that gcd(i, j) = 1.

we can calculate it in min(n, m) with mebius function.

answer[i] = m[i] * f[i], where m[i] — value of mebius function(i), f[i] = function returning answer for i. in this problem it's (M / i) * (N / i)

→ Reply