1621. Сумма от 1 до n

Сумму всех целых чисел от 1 до 100 можно посчитать при помощи хитрого приёма. Разобьём все числа по парам 1 и 100, 2 и 99, 3 и 98 и т.д. Сумма каждой пары 101. Пар всего 100 / 2 = 50. Поэтому сумма равна (1 + 100) * 100 / 2. Для нечётного количества слагаемых работает та же формула, например: 1 + 2 + 3 = (1 + 3) * 3 / 2 = 6.

Вход. Одно целое число n.

Выход. Сумма всех целых чисел от 1 до n. Гарантируется, что ответ помещается в 64-битовый знаковый целочисленный тип.

Пример входа	Пример выхода
100	5050

РЕШЕНИЕ

элементарная задача – формула

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

По формуле суммы членов арифметической прогрессии искомая сумма равна

Однако она справедлива для n ≥ 1. При n < 1 количество слагаемых от 1 до n равно |n| + 2 и формула суммы примет вид

Непосредственное суммирование в цикле даст Time Limit.

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

Определим функцию вычисления модуля числа.

long long abs(long long x)

{

return (x < 0) ? -x : x;

}

Читаем входное значение n. Вычисления будем производить в 64-битовом знаковом целочисленном типе. Формула суммы включает в себя два множителя и один делитель. Чтобы избежать переполнения, будем сначала выполнять деление, а затем умножение.

scanf("%lld",&n);

if (n >= 1)

{

if (n % 2) res = (1 + n) / 2 * n;

else res = n / 2 * (1 + n);

}

else

{

if (n % 2) res = (1 + n) / 2 * (abs(n) + 2);

else res = (abs(n) + 2) / 2 * (1 + n);

}

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

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