5897. Сумма квадратов

Для заданных целых чисел n и m вычислить сумму квадратов всех целых чисел, расположенных между n и m включительно. Ответ вывести по модулю 10⁹ + 9.

Вход. Два числа n и m (-10¹⁷ ≤ n, m ≤ 10¹⁷).

Выход. Вывести ответ задачи.

Пример входа	Пример выхода
2 -2	10

РЕШЕНИЕ

математика

Анализ алгоритма

Воспользуемся формулой для суммы квадратов:

S(n) = 1² + 2² + … + n² =

Установим сначала границы суммирования так, чтобы было n ≤ m. Если при этом m ≤ 0, то интервал суммирования [n; m] поменяем на [-m; -n].

Итак, у нас n ≤ m и m ≥ 0. Если n ≥ 0, то искомая сумма равна S(m) – S(n – 1).

Если n ≤ 0, то искомая сумма равна S(m) + S(-n).

Реализация алгоритма

Определим константу модуля.

#define MOD 1000000009

Функция sum вычисляет сумму квадратов 1² + 2² + … + n² по формуле, приведенной в анализе задачи. Чтобы избежать переполнения при умножении, сначала сократим на 6 числитель дроби, после чего совершим умножение.

long long sum(long long n)

{

long long a = n % MOD;

long long b = (n + 1) % MOD;

long long c = (2*n + 1) % MOD;

Поскольку n или n + 1 делится на 2, то разделим четный множитель на 2.

if (a % 2 == 0) a = a / 2; else b = b / 2;

Один из множителей a = n, b = n + 1 или c = 2n + 1 обязательно делится на 3, разделим его на 3.

if (a % 3 == 0) a = a / 3; else

if (b % 3 == 0) b = b / 3; else c = c / 3;

Найдем произведение оставшихся после сокращения множителей.

return (((a * b) % MOD) * c) % MOD;

}

Основная часть программы.

scanf("%lld %lld",&n,&m);

if (n > m) {temp = n; n = m; m = temp;}

if (m < 0) {temp = n; n = -m; m = -temp;}

if (n >= 0)

res = (sum(m) - sum(n-1) + MOD) % MOD;

else

res = (sum(m) + sum(-n)) % MOD;

Выводим ответ.

printf("%lld\n",res);