Description
描述
Little Johnny likes to draw a lot. A few days ago he painted lots of straight lines on his sheet of paper. Then he counted in how many zones the sheet of paper was split by these lines. He noticed that this number is not always the same. For instance, if he draws 2 lines, the sheet of paper could be split into 4, 3 or even 2 (if the lines are identical) zones. Since he is a very curious kid, he would like to know which is the maximum number of zones into which he can split the sheet of paper, if he draws N lines. The sheet of paper is to be considered a very large (=infinite) rectangle.
小Johnny非常喜欢画画。几天前，他在一张纸上画了很多直线。接下去他要数这些直线将平面分成了多少个空间。他注意到这个数字在多数情况下并不是相同的。例如，如果画2条线，这张纸可能被分成4、3、2（如果这2条线完全重合的话）个空间。以为他是一个非常聪明的孩子，他希望知道如果他画N条线，最多能够把平面分成多少个空间。这张纸可以认为是一个非常（无穷）大的矩形。
Input
输入
The input file will contain an integer number: N (0<=N<=65535).
输入文件包含一个整数N（0<=N<=65535）。
Output
输出
You should output one integer: the maximum number of zones into which the sheet of paper can be split if Johnny draws N lines.
你需要输出一个整数：如果Johnny画N条线，这张纸能够被分成的最多的平面数。
Sample Input #1
样例输入 #1
0
Sample Output #1
样例输出 #1
1
Sample Input #2
样例输入 #2
1
Sample Output #2
样例输出 #2
2
Analysis
分析
数学题。直线分平面数，我们也可以通过找规律的方法来求出它的公式：
| 线段数N | 平面数M |
| 0 | 1 |
| 1 | 1 + 1 = 2 |
| 2 | 2 + 2 = 4 |
| 3 | 4 + 3 = 7 |
| 4 | 7 + 4 = 11 |
| 5 | 11 + 5 = 16 |
| 6 | 16 + 6 = 22 |
根据上表，我们可以很容易的求得递推公式：MN = MN-1 + N。
由此得到通项公式：M = N * (N + 1) / 2 + 1。
当然我们也可以使用数学归纳法证明这个结论。
Solution
解决方案
#include <iostream>
using namespace std;
typedef unsigned long long ull;
int main()
{
int N;
cin >> N;
cout << (ull)N * (N + 1) / 2 + 1;
return 0;
}
本题需要注意的是给出的数据范围如果不使用unsigned long long会溢出，因此必须使用unsigned long long。