[数据结构与算法]h0152. 故事计算题（计蒜客——西邮K题）解析

小米给小宝讲了一个小故事。从前有座山，山上有N个庙，每个庙里有1个老和尚和N+1个小和尚。山中流传着一个故事：从前有座山，山上有N+1个庙，每个庙里有1个老和尚和N+2个小和尚。山中流传着一个故事：从前有座..........从前有座山，山上有M个庙，每个庙里有1个老和尚和M+1个小和尚。小宝听完这个故事后想知道一共有多少个小和尚？

输入格式:

第一行有一个正整数K。
接下来有K行，每行有两个数N，M。
数据保证1≤K≤100 000,0≤N，M<1 000 000。

输出格式:

输出K行，表示结果

输入样例:

2
1 3
2 4

输出样例:

20
38

思路1：

ll ans = 0;
for(int i = n;i<=m;i++)
    ans += i * (i+1)

但看一下数据范围————》难逃T

思路2:(找规律)
1 * 2 = 2

2 * 3 = 6

3 * 4 = 12

4 * 5 = 20

.......

得到规律

第n项是：n*(n+1);

前n项和：n*(n+1)*(n+2)/3;

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int k;
    scanf("%d",&k);
    while(k--)
    {
        int n,m;
        scanf("%d %d",&n,&m);
        n--;
        ll a = n*(n+1)*(n+2)/3;
        ll b = m*(m+1)*(m+2)/3;
        printf("%lld\n",b-a); 
    }
}