GETTING AN AP
Below given python code for APPROB spoj or GETTING AN AP spoj.
For understanding write some small test case like for 3 ,4, 5, you will get the logic if you are unable to get you can mail me @ raj.nishant360@gmail.com
Let’s take N=3 so the content in the three boxes will be as follow
1

1

1

2

2

2

3

3

3


4

4


5

5


6

6


7



8



9

So from the table we are first counting the AP with nonnegative common difference.
1> we choose “1” from the first raw. Then total possible AP will be
1> 
1 
1 
1 
2> 
1 
2 
3 
3> 
1 
3 
5 
4> 
1 
4 
7 
5> 
1 
5 
9 
For “1” (selected in first row) there are total five AP possible
For “1” (selected in first row) there will be no AP possible with negative common difference
2> For “2” (selected in first row)
1> 
2 
2 
2 
2> 
2 
3 
4 
3> 
2 
4 
6 
4> 
2 
5 
8 
So for “2” (selected in first row) we will have total four AP as shown in table.
For two no AP exits in table for negative common differencs.
2> For “3” (selected in first row)
1> 
3 
3 
3 
2> 
3 
4 
5 
3> 
3 
5 
7 
4> 
3 
6 
9 
So for “3” (selected in first row) we will have four AP as shown in table.
Here for three there will be one AP with negative common difference.
3 
2 
1 
Now for N=3;
We will sum all the possible AP (5+5+4) = 14;
Now total probability of selecting random number from three boxes will be>
(1/N)*(1/2N)*(1/3N) = 1/6N^{3}
So our answer will be = 14 *(1/6N^{3}) = 14*(1/162) = 7/81;
Now we generalize the above concept. Let “X” be any number in 2^{nd} column and “I” be any number in 1^{st} column the AP will exist if an only if bellow condition is satisfied for nonnegative common difference.
X + (XI) <=3N > 2X – I <=3N > X <=(3N + I)/2 Floor of this will give maximum X for which AP can be formed . Total AP (with nonnegative common difference ) can be formed by choosing “I” will be
MAX (“X”) for given “I” till which AP can be constructed  “I” +1(I,I,I will itself form an AP with CD=0)
So it will be (3N +I)/2 – I +1 > ( (3N+2) – i)/2 ; Floor of this will give you the total number of AP possible for selected “I” in first column .
F(i) = ( (3N+2) – i)/2
This is for nonnegative common difference for negative try yourself .
Now if we select N=5 then total number of divisor will be (calculated by F1)
N = 1 > F(1) = 8;
N= 2 > F(2) = 7;
N= 3 > F(3) = 7;
N= 4 >F(4)= 6;
N= 5 >F(5) = 6;
This is for nonnegative CD for negative CD
N = 1 > 0;
N= 2 > 0;
N= 3 > 1;
N= 4 > 1;
N= 5 > 2;
As series are forming in both the case CD +ive and –ive so we can easily calculate the sum in O(1) time
from fractions import gcd import sys t=int(sys.stdin.readline()) while t: n=int(sys.stdin.readline()) if n&1: start = (3*n+1)//2 st = (n1)//2 end = (3*n  n +2)//2 total = 6*n*n*n result = start + 2*(((start1)*start)//2  ((end1)*end)//2) result = result + st + (st1)*st g= gcd(total,result) l="" l=l+str(result//g)+"/"+str(total//g) print (l) else : start = (3*n+1)//2 st = (n1)//2 end = (3*n  n +2)//2 total = 6*n*n*n result =2*(((start+1)*start)//2  ((end1)*end)//2) result = result + st*(st+1) g= gcd(total,result) l="" l=l+str(result//g)+"/"+str(total//g) print (l) t=1