CodeSky 代码之空

随手记录自己的学习过程

蓝桥杯 入门训练 序列求和

2015-12-27 21:53分类: Java评论: 0

这一道题本来应该很简单:

求1+2+3+...+n的值。

简单吧,一个循环就能搞定,看上去是这样,但是事实上,我们要注意到数据规模:

1 <= n <= 1,000,000,000。

本题直接的想法是直接使用一个循环来累加,然而,当数据规模很大时,这种“暴力”的方法往往会导致超时。此时你需要想想其他方法。你可以试一试,如果使用1000000000作为你的程序的输入,你的程序是不是能在规定的上面规定的时限内运行出来。

嗯,那么就会遇到运行的问题。但是这种东西有什么好方法么——答案是,有的,名为等差数列求和公式的东西。

讲到这里,基本上大家也发现了,许多题都是在考你的数学能力。

Well,那么现在,我们就知道要怎么做了:

1import java.util.*;
2
3public class Sum {
4	public static void main(String[] args) {
5		Scanner in = new Scanner(System.in);
6
7		long n = in.nextLong();
8		long sum = 0;
9/*
10		for (long i = 1; i <= n; i++) {
11			sum += i;
12		}
13*/		
14
15		sum = (1 + n) * n / 2;
16
17		System.out.println(sum);
18	}
19}
20

评论 (0)