2860.
Sum of integers on the interval
Find the sum of all
integers on the segment from a to b, inclusive.
Input. Two integers à and b, each with absolute value not exceeding 2 * 109.
Output. Print the sum of all
integers on the segment from a to b, inclusive.
|
Sample
input |
Sample
output |
|
2 5 |
14 |
SOLUTION
elementary computations
Algorithm analysis
If the sum is computed
using a loop, then in the worst case (when a = -2 * 109 and b = 2 * 109) up to 4 * 109
iterations
would be required, which would lead to a time limit exceeded error. Therefore,
we use the formula for the sum of an arithmetic progression. The first term is a, the last term is b, and the number of terms is b – a + 1. Then the required sum is computed
using the formula:
It should also be noted
that the resulting value may not fit into the int type, so the long long type must be used for the
computations.
Algorithm implementation
Read the input data.
scanf("%lld
%lld",&a,&b);
Compute and print the answer.
res = (a + b) * (b - a + 1) / 2;
printf("%lld\n",res);
Java implementation
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 implementation
Read the input data.
a, b = map(int,input().split())
Compute and print the answer.
res = (a + b) * (b - a + 1) // 2
print (res)