歐拉定理 V-E+F=C+1
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?
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 S sets of input. Each input contains one integer N
(0<=N<2^31)<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vc3Ryb25nPi48L3A+CjxwPiA8L3A+CjxwPjxzdHJvbmc+T3V0cHV0PC9zdHJvbmc+PC9wPgo8cD5Gb3IgZWFjaCBzZXQgb2YgaW5wdXQgeW91IHNob3VsZCBvdXRwdXQgaW4gYSBzaW5nbGUgbGluZSB0aGUgbWF4aW11bSBudW1iZXIgcGllY2VzIG9mIGxhbmQgcG9zc2libGUgdG8gZ2V0IGZvciB0aGUgdmFsdWUgb2YgPHN0cm9uZz5OPC9zdHJvbmc+LjwvcD4KPHA+PHN0cm9uZz4gPC9zdHJvbmc+PC9wPgo8cD48c3Ryb25nPlNhbXBsZSBJbnB1dDo8L3N0cm9uZz48L3A+CjQ8YnI+CjE8YnI+CjI8YnI+CjM8YnI+CjQ8YnI+Cjxicj4KPHA+IDwvcD4KPHA+PHN0cm9uZz5TYW1wbGUgT3V0cHV0Ojwvc3Ryb25nPjwvcD4KMTxicj4KMjxicj4KNDxicj4KODxicj4KCjxociBzaXplPQ=="2" width="100%" align="center">
Shahriar Manzoor
/**
* Created by ckboss on 15-2-1.
*/
import java.math.BigInteger;
import java.util.*;
public class Main {
BigInteger pfh(BigInteger n){
return n.multiply((n.add(BigInteger.ONE))).multiply((n.multiply(BigInteger.valueOf(2))).add(BigInteger.ONE)).divide(BigInteger.valueOf(6));
}
BigInteger getV(BigInteger n){
BigInteger A = n.subtract(BigInteger.valueOf(2));
BigInteger B = n.subtract(BigInteger.valueOf(3));
BigInteger temp = A.multiply(B).divide(BigInteger.valueOf(2)).multiply(A).subtract(pfh(B));
temp = temp.multiply(n).divide(BigInteger.valueOf(4));
return temp.add(n);
}
BigInteger getE(BigInteger n){
BigInteger A = n.subtract(BigInteger.valueOf(2));
BigInteger B = n.subtract(BigInteger.valueOf(3));
BigInteger temp = A.multiply(B).divide(BigInteger.valueOf(2)).multiply(A).subtract(pfh(B)).add(n).subtract(BigInteger.ONE);
temp = temp.multiply(n).divide(BigInteger.valueOf(2));
return temp.add(n);
}
Main(){
Scanner in = new Scanner(System.in);
int T_T = in.nextInt();
while(T_T-->0) {
BigInteger n = in.nextBigInteger();
BigInteger V = getV(n);
BigInteger E = getE(n);
BigInteger F = BigInteger.ONE.subtract(V).add(E);
System.out.println(F);
}
}
public static void main(String[] args){
new Main();
}
}
