Marwan58's blog

Help with a problem
By Marwan58, history, 4 years ago, In English

Is there an efficient way to calculate the sum of lcm(x,y) for every value x and y such that 1<=x<=n && 1<=y<=n with a given n ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Mobius Inversion

You can also do dp where you dp[i] is sum of all x * y numbers with gcd(x, y) equal to i, and to transition u find with basic math sum of all x * y with gcd(x, y) >= i by taking sum of all multiples of i and squaring it like sieve then in sieve like fashion subtract out dp values that are multiples of i as that gets rid of overcounting. Obviously you then just take sum of dp[i] / i for all dp values. I'm p sure this dp method and mobius inversion are almost always interchangeable but not sure...

→ Reply