TOP

ACM1001:Sum Problem
2019-03-10 22:08:01 】 浏览:141次 本网站的内容取自网络,仅供学习参考之用,绝无侵犯任何人知识产权之意。如有侵犯请您及时与本人取得联系,万分感谢。
Tags:ACM1001 Sum Problem

Problem Description
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
 ------------------------------------------------------------------------------------------------------------------
Sn = n*(n+1)/2
把两个相同的自然数列逆序相加
2Sn=1+n + 2+(n-1) + 3+(n-2) + ... n+1
=n+1 +n+1 + ... +n+1
=n*(n+1)
Sn=n*(n+1)/2
另,
m到n的自然数之和:Smn=(n-m+1)/2*(m+n)
(n>m)
Smn=Sn-S(m-1)
=n*(n+1)/2 -(m-1)*(m-1+1)/2
={n*(n+1) - m(m-1)}/2
={n*(n+1) - mn + m(1-m) + mn }/2
={n*(n-m+1)+ m(1+ n-m)}/2
=(n+m)(n-m+1)/2
注意:虽然题目说sum不会大于32位,但是n*(n+1)会大于32位。
 
#include <stdio.h>
#include <stdlib.h>

int main()
{
    long long n;
    //freopen("F:\\input.txt", "r", stdin);
    while (scanf("%lld", &n) != EOF)
    {
        printf("%lld\n\n", n * (n + 1) / 2);
    }
    //freopen("CON", "r", stdin);
    //system("pause");
    return 0;
}

  

请关注公众号获取更多资料


ACM1001:Sum Problem https://www.cppentry.com/bencandy.php?fid=45&id=212574

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇h264文件分析(纯c解析代码) 下一篇C语言程序

评论

验 证 码:
表  情:
内  容: