Блог пользователя sumit93

Number theory
Автор sumit93, 10 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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)

→ Ответить