2860.
Сумма чисел на промежутке
Найдите сумму всех целых
чисел на отрезке от a до b включительно.
Вход. Два целых числа а
и b, абсолютное значение каждого из
которых не превышает 2 * 109.
Выход. Выведите сумму всех целых чисел на отрезке от a до b включительно.
|
Пример
входа |
Пример
выхода |
|
2 5 |
14 |
РЕШЕНИЕ
элементарные вычисления
Анализ алгоритма
Если вычислять сумму с
помощью цикла, то в худшем случае (при a = -2 * 109 и b = 2 * 109)
потребуется
выполнить до 4 * 109 итераций, что приведёт к превышению лимита
времени. Поэтому воспользуемся формулой суммы арифметической прогрессии. Первый
член равен a, последний b, а количество членов равно b – a + 1. Тогда
искомая сумма вычисляется по формуле:
Также следует отметить,
что полученное значение может не помещаться в тип int, поэтому при вычислениях необходимо
использовать тип long long.
Реализация алгоритма
Читаем входные данные.
scanf("%lld
%lld",&a,&b);
Вычисляем и выводим ответ.
res = (a + b) * (b - a + 1) / 2;
printf("%lld\n",res);
Java реализация
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
long a = con.nextLong();
long b = con.nextLong();
long res = (a + b) * (b - a + 1) / 2;
System.out.println(res);
}
}
Python реализация
Читаем входные данные.
a, b = map(int,input().split())
Вычисляем и выводим ответ.
res = (a + b) * (b - a + 1) // 2
print (res)