Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

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

Автор Minimalistic, история, 6 лет назад, По-английски

you have an an integer n such that 1<=n<= 10^12, find the sum of all triagular numbers that are less than or equal n,

time limit: 1 second

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

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

just binary search the index of the last triangular number <=n and use the hockey stick theorem

»
6 лет назад, # |
Rev. 5   Проголосовать: нравится -24 Проголосовать: не нравится

It can be solved in O(sqrt(n)). Triangular numbers is T(k)=k(k+1)/2, just increment k from 1 while T(k)<=n and get a sum of T(k)

If you have q queries, it can be solved in O(q*log(n)+sqrt(n)) with precompute prefix sums. Code?

And you can use binary search by last T(k), sum of T(k) from 1 to m is m(m+1)(m+2)/6

And you can solve in O(1) by solving equation m * (m+1) / 2 <= n ~ m^2 + m - 2 * n = 0.

Solution: m = (sqrt(8*n+1)-1)/2

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -36 Проголосовать: не нравится

    yes please, I would like to see you approach

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится
      One query in `O(sqrt(n))`
      One query in `O(1)`
      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 4   Проголосовать: нравится +8 Проголосовать: не нравится

        I like that O(1) query, another thing that could be done here instead of using formula sqrt(8 * n + 1) — 1) / 2; it can be subs. by the following two lines of codes, 1-x=floor(sqrt(2*n)); 2-if(((x+1)*(x))/2>n)--x; x here is the number of the first triangular numbers <= n, then what is left is to calculate the sum of the first x triangular numbers. x=floor(sqrt(2*n));if(((x+1)*(x))/2>n)--x;

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

What's going on here? It is attack from one user with 15 accounts?