sum of triangular numbers

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

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

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

Minimalistic
8 лет назад
10

Комментарии (8)

Показать архивные | Написать комментарий?

peanutpedo20

8 лет назад, скрыть # |

+18

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

→ Ответить

Minimalistic

8 лет назад, скрыть # ^ |

-36

did not understand hockey stick theorem, could you explain it please? how does it relate to the problem?

→ Ответить

peanutpedo20

8 лет назад, скрыть # ^ |

+34

sum of first i triangular numbers is the ith tetrahedral number

→ Ответить

dmkozyrev

8 лет назад, скрыть # |

← 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

→ Ответить

Minimalistic

8 лет назад, скрыть # ^ |

← Rev. 2 →

-36

yes please, I would like to see you approach

→ Ответить

dmkozyrev

8 лет назад, скрыть # ^ |

← Rev. 2 →

-10

One query in `O(sqrt(n))`

#include <iostream>
#include <vector>
#include <algorithm>
 
typedef long long ll;
 
ll solve(ll n) {
	ll answ = 0;
	for (int i = 0; ll(i) * (i+1) / 2 <= n; ++i) {
		answ += ll(i) * (i+1) / 2;
	}
	return answ;
}
 
int main() {
	ll n; std::cin >> n;
	std::cout << solve(n);
	return 0;
}

One query in `O(1)`

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

typedef long long ll;

ll solve(ll n) {
    ll last = (std::sqrt(8 * n + 1) - 1) / 2;
    while (last * (last+1) / 2 > n) --last;
    while ((last+1) * (last+2) / 2 <= n) ++last;
    return last * (last+1) / 2 * (last+2) / 3;
}

int main() {
    ll n; std::cin >> n;
    std::cout << solve(n);
    return 0;
}

→ Ответить

Thinker150485

8 лет назад, скрыть # ^ |

← Rev. 4 →

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;

→ Ответить