Задача из республиканской олимпиады по информатике

"Простая математика" (День 1. Задача 1)

Условие:

Посчитать сумму первых n членов последовательности:

S(n) = (f(1) + g(1)) + (f(2) + g(2)) + (f(3) + g(3)) + ... + (f(n) + g(n)),

где f(a) возвращает корень квадратный sqrt(a), округлённый вверх,

g(a) возвращает корень кубический 3&sqrt(a), округлённый вниз

Т.е.:

f(5) = 3

f(4) = 2

f(3) = 2

g(5) = 1

g(9) = 2

g(26)= 2

Входные данные:

Число N <= 10^12

Выходные данные:

Результат S(N). Гарантируется, что S(N) <= 10^18

Пример ввода:

4

Пример вывода

11

(Т.к. S(4) = ((f(1) + g(1)) + (f(2) + g(2)) + (f(3) + g(3)) + (f(4) + g(4))) = (1 + 1) + (2 + 1) + (2 + 1) + (2 + 1) = 2 + 3 *3 = 2 + 9 = 11)

Пример ввода:

5

Пример вывода

15

(Т.к. S(5) = S(4) + (f(5) + g(5)) = 11 + (3 + 1) = 15

/-----------------------------------------

Решение:

Общая формула

Или такая

/-----------------------------------------

/*вторая формула на с++*/
/*решение пройдено на 100%*/
сin >> n;
m = (long long)(sqrt(n));
k = (long long)(pow(n, 1.0/3) + 0.0005);    // + 0.0005 из-за неточности работы pow()
sum  = m * (m + 1) * (4 * m — 1) / 6;
sum += (m + 1) * (n — m * m);
sum += k * (k + 1) * (k + 1) * (3 * k + 4) / 4;
sum -= k * (pow((k + 1), 3) — n — 1);
сout << sum;

/-----------------------------------------

Прим:

Формула 1:

m = [sqrt(n)]

k = [3&sqrt(n)]

S(n) = n(m+1) — m(m+1)(2m+1)/6 + k(n+1) — (k(k+1)/2)^2

Формула 2:

S(n) = m(m+1)(4m-1)/6 + (m+1)(n-m^2) + k(k+1)^2(3k+4)/4 — k((k+1)^3 — n — 1)