HDU-1249 三角形（递推）

Description

用N个三角形最多可以把平面分成几个区域?

Input

输入数据的第一行是一个正整数T(1<=T<=10000),表示测试数据的数量.然后是T组测试数据,每组测试数据只包含一个正整数N(1<=N<=10000).

Output

对于每组测试数据,请输出题目中要求的结果.

Sample Input

2
1
2

Sample Output

2
8

---

当n=1的时候，最多分成两个区域，当n = 2的时候，最多分成8个区域。规律其实就是后面的每条线和前面n-1个三角形的两边相交，三个边都遵循这个规律，于是得到递推关系： $$ a_n = a_{n - 1} + 3\times(2\times (n- 1 ) - 1) + 3 \ a_n = 3n^2 - 3n + 8 $$

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>

using namespace std;


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int caseNum; cin >> caseNum;
    while (caseNum--) {
        int n; cin >> n;
        cout << (3 * n * n - 3 * n + 2) << endl;
    }

    return 0;
}