Pleasant pairs -> O(n log n)

Правка en1, от akzytr, 2024-04-30 07:03:29

This problem:1541B - Pleasant Pairs

Editorial has the following statements:

Number of pairs(a, b) such that a*b <= 2*n is equal to

2n / 1 + 2n/2 ... where the denominator goes till 2*n.

Time complexity is said to be o(n log n), it did mention harmonic numbers, however I am having a hard time making the connection? Is this somehow in context to https://codeforces.com/blog/entry/118001 where they explain upper bound?

Any help appreciated

Теги math

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский akzytr 2024-04-30 07:03:29 482 Initial revision (published)