MAX11189's blog

By MAX11189, history, 2 years ago, In Russian

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

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

| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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$$$).