Bubble Sort

Check the following code which counts the number of swaps of bubble sort.

int findSwaps( int n, int a[] )
{
    int count = 0, i, j, temp, b[100000];

    for( i = 0; i < n; i++ ) {
        b[i] = a[i];
    }
    for( i = 0; i < n; i++ ) {
        for( j = 0; j < n - 1; j++ ) {
            if( b[j] > b[j+1] ) {
                temp = b[j];
                b[j] = b[j+1];
                b[j+1] = temp;

                count++;
            }
        }
    }
    return count;
}

You have to find the average value of 'count' in the given code if we run findSwaps() infinitely many times using constant 'n' and each time some random integers (from 1 to n) are given in array a[]. You can assume that the input integers in array a[] are distinct.

Input 

Input starts with an integer T (1000), denoting the number of test cases. Each test case contains an integer n ( 1n10⁵) in a single line.

Output 

For each case, print the case number and the desired result. If the result is an integer, print it. Otherwise print it in 'p/q' form, where p and q are relative prime.

Sample Input 

2
1
2

Sample Output 

Case 1: 0
Case 2: 1/2

---

兩個數字交換的期望值是 1/2
那麼 n 個數字交換的次數為 n(n-1)/2
總共的期望值是 1/2 * n(n-1)/2

#include <stdio.h>
typedef long long Int64;
struct frac {
	Int64 num, den;
	void print() {
		simpler();
		if(den != 1)
			printf("%lld/%lld\n", num, den);
		else
			printf("%lld\n", num);;
	}
	void simpler() {
		Int64 g = gcd(num, den);
		num /= g;
		den /= g;
	}
	Int64 gcd(Int64 x, Int64 y) {
		if(x == 0)	return y;
		if(y == 0)	return x;
		Int64 tmp;
		while(x%y) {
			tmp = x, x = y, y = tmp%y;
		}
		return y;
	}
};
int main() {
	int t, Case = 0;
	Int64 n;
	scanf("%d", &t);
	while(t--) {
		scanf("%lld", &n);
		printf("Case %d: ", ++Case);
		frac f = {n*(n-1), 4};
		f.print();
	}
    return 0;
}