ACM程序设计选修课——1051: Glamor Sequence（YY+求和公式）

1051: Glamor Sequence

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 16  Solved: 5
[Submit][Status][Web
Board]

Description

you have a sequence +1, +2, +3, ... +m, -(m + 1), -(m + 2), ..., -(2m), (2m + 1), (2m + 2), ..., (3m), .....
and you need calculator sum of the first n items.

Input

For each test case, there is a line contains two integers n and m, (1 <= m <= n <= 1000000000).

Output

For each test case, print sum of the first n items.

Sample Input

8 2

10 3

Sample Output

-8

5

HINT

For the first sample, the sequence is 1, 2, -3, -4, 5, 6, -7, -8, so the answer is -8.

For the second sample, the sequence is 1, 2, 3, -4, -5, -6, 7, 8, 9, -10, so the answer is 5.

想了很久还是不会。问了同学大概思路，确是用等差数列求和公式，但是先前的做法效率比较低，用了for循环，一旦出现n比较大而m非常小的话就会超时，比如n=1000000000，m=1，test测试一下5秒多。

因此一种思路是这样：

可以发现从1开始前2*m项的和的绝对值是一个常数即m，e=n-n%(2*m)那么只需处理后面e+1~n的数字即可。因此可以有如下规律

设剩下的区间为e+1~n（也可能是e+m）。

1、若e+m<=n——即数轴分布情况为e+1~e+m~n。只需将之前的所有完整段的和加上Sum[e+1,e+m]即可，且每一项都是正数。

2、若e+m>n——即数轴分布情况为e+1~n~e+m。那么要计算S1[e+1,n]与S2[n+1,e+m]，ans=ans+S1-S2。

代码：

#include<iostream>

#include<string>

#include<algorithm>

using namespace std;

int main(void)

{

    long long n,m,e;

    long long ans;

    while (~scanf("%lld%lld",&n,&m))

    {

        e=n-n%(2*m);

        ans=(e)*(-m)/2;//所有完整段求和

        if(e+m<n)//分类讨论

        {

        	ans=ans+(2*e+1+m)*m/2;

        	ans=ans-(e+m+1+n)*(n-e-m)/2;

        }

        else if(e+m>n)

        {

        	ans=ans+(e+1+n)*(n-e)/2;

        }

        else

        {

        	ans=ans+(2*e+1+m)*m/2;

        }

    	printf("%lld\n",ans);//这题要用long long来储存答案

    }

    return 0;

}