首页 > 代码库 > [HDU1001] Sum Problem

[HDU1001] Sum Problem

Problem Description

 

Hey, welcome to HDOJ(Hangzhou Dianzi University Online Judge).

 

In this problem, your task is to calculate SUM(n) = 1 + 2 + 3 + ... + n.

 

Input

 

The input will consist of a series of integers n, one integer per line.

 

Output

 

For each case, output SUM(n) in one line, followed by a blank line. You may assume the result will be in the range of 32-bit signed integer.

 

Sample Input

 

1
100
 

Sample Output

 

1

 

5050

 

分析

 

输入n,求1+2+...+n的和。

 

方法有两种:

 

1. 直接求法

 

使用一个for循环进行累加。用s表示总和,s初始化为0,然后再维护一个循环变量i。代码:

 

int s = 0;
for (int i = 1; i <= n; i++)
    s += i;
printf("%d\n\n", s);

 

完整C程序:

 

#include <stdio.h>
int main()
{
    int n;
    while (scanf("%d", &n) != EOF)
    {
        int s = 0;
        for (int i = 1; i <= n; i++)
            s += i;
        printf("%d\n\n", s);
    }
    return 0;
}

 

2. 公式法

 

还记得高斯吧,他小时候就计算出了1+2+...+100=5050。方法1就像是其他同学,方法2则是高斯。

 

进入正题,等差数列有一个公式:总和=(首项+末项)*项数/2。这里首项=1,末项=n,项数=n,因此1+2+...+n=(1+n)*n/2。代码:

 

printf("%lld\n\n", (long long)(1 + n) * (long long)n / 2LL);

 

但有一个类型问题需要注意:description中说总和是不超过32位有符号整数的范围的(也就是2^31-1或2147483647),这说明(1+n)*n/2<=2147483647,但不代表(1+n)*n也是小于2147483647的。事实上,当n>=14654时,(1+n)*n就超过2147483647了。这种情况下,进行运算将会出现溢出错误。因此需要将1+n和n转换成long long(其实只要转1个就可以了,后面的2LL也可以直接写2)。当然,算出(1+n)*n后将其转成int再用%d打印也没有问题。(P.S. 我就是因为这个原因WA的……)

 

完整C程序:

 

#include <stdio.h>
int main()
{
    int n;
    while (scanf("%d", &n) != EOF)
        printf("%lld\n\n", (long long)n * (long long)(n + 1) / 2LL);
    return 0;
}

 

注意

 

每次输出要输出两个换行符!

[HDU1001] Sum Problem