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

Автор MAX11189, история, 2 года назад, По-русски

Can anybody please explain me how to solve this problem, couse tutorial is very bad and not understandable:(

https://mirror.codeforces.com/problemset/problem/1541/B

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

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

Which part of editorial you didn't understand? I see this parts:

  1. $$$a_i * a_j = i + j <= 2n$$$
  2. So you can brute force all pairs for which $$$a_i * a_j <= 2n$$$
  3. For each $$$i$$$ you try values $$$k$$$ for which $$$a_i * k <= 2n$$$ and check if $$$a_{a_i * k - i} = k$$$
  4. You would iterate over $$$O(nlogn)$$$ pairs because for each $$$i$$$ you iterate $$$2n / a_i$$$ pairs. All $$$a_i$$$ distinct so it would be no more than $$$2n / 1 + 2n / 2 + 2n / 3 + ... = 2n(1 + 1 / 2 + 1 / 3 + ... + 1 / n) = O(nlogn)$$$ (Braced expression is harmonic series and it is $$$logn + some~constants$$$).