POJ ACM习题【No.2924】

Gauß in Elementary School Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 5129 Accepted: 2259

Description

Johann Carl Friedrich Gauß (1777 – 1855) was one of the most important German mathematicians. For those of you who remember the Deutsche Mark, a picture of him was printed on the 10 – DM bill. In elementary school, his teacher J. G. Büttner tried to occupy the pupils by making them add up the integers from 1 to 100. The young Gauß surprised everybody by producing the correct answers (5050) within seconds.

Can you write a computer program that can compute such sums really quickly?

Given two integers n and m , you should compute the sum of all the integers from n to m . In other words, you should compute

Input

The first line contains the number of scenarios. Each scenario consists of a line containing the numbers n and m (−10⁹ ≤ n ≤ m ≤ 10⁹ ).

Output

The output for every scenario begins with a line containing “Scenario # i : ”, where i is the number of the scenario starting at 1. Then print the sum of all integers from n to m . Terminate the output for the scenario with a blank line.

Sample Input

3 1 100 -11 10 -89173 938749341

Sample Output

Scenario #1: 5050 Scenario #2: -11 Scenario #3: 440625159107385260

 

要注意最大值的限制，虽然最大的输入在Int范围内，但是结果值将远远超过Int取值范围

 

import java.util.*; import java.math.*; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); int num = Integer.valueOf(cin.nextLine()).intValue(); for(int i = 0; i < num; i++) { String[] str = cin.nextLine().split(" "); BigInteger a = new BigInteger(str[0]); BigInteger b = new BigInteger(str[1]); BigInteger result = new BigInteger("0"); if((a.intValue() >= 0 && b.intValue() >= 0) || (a.intValue() < 0 && b.intValue() < 0)) { int times = (Math.abs(b.intValue()-a.intValue())+1); result = result.add(a); result = result.add(b); result = result.multiply(new BigInteger(times + "")); result = result.divide(new BigInteger("2")); } else { int times1 = (Math.abs(b.intValue()-0)+1); BigInteger r1 = new BigInteger("0"); r1 = r1.add(b); r1 = r1.multiply(new BigInteger(times1 + "")); r1 = r1.divide(new BigInteger("2")); int times2 = (Math.abs(a.intValue()-0)+1); BigInteger r2 = new BigInteger("0"); r2 = r2.add(a); r2 = r2.multiply(new BigInteger(times2 + "")); r2 = r2.divide(new BigInteger("2")); result = r1.add(r2); } System.out.println("Scenario #" + (i+1) + ":"); System.out.println(result.toString()); if(i != num-1) System.out.println(); } } }