首页 / 软件开发 / 数据结构与算法 / UVa 10213 How Many Pieces of Land ？ （数学&欧拉公式&高精度）

UVa 10213 How Many Pieces of Land ？ （数学&欧拉公式&高精度）2014-07-22 csdn博客 synapse710213 - How Many Pieces of Land ？

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&page=show_problem&problem=1154

You are given an elliptical shaped land and you are asked to choose n arbitrary points on its boundary. Then you connect all these points with one another with straight lines （that’s n*（n-1）/2 connections for n points）. What is the maximum number of pieces of land you will get by choosing the points on the boundary carefully？

Fig: When the value of n is 6.

Input

The first line of the input file contains one integer S （0 < S < 3500）, which indicates how many sets of input are there. The next S lines contain Ssets of input. Each input contains one integer N （0<=N<2^31）.

Output

For each set of input you should output in a single line the maximum number pieces of land possible to get for the value of N.

Sample Input:

4

1

2

3

4

Sample Output:

1

2

4

8

《入门经典》 P86上的一道好题，我这里把O（1）的公式算出来了。