1408.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1408 on 2005-03-23 at 23:44:10 */ 
#include <stdio.h>
#include <math.h>

int combinat(int, int);
int gbc(int, int);

int main()
{
    int n, total, num[50], comfac;
    int i, j;
    double pi;
    
    while(scanf("%d", &n) == 1){
        if(n == 0){
            return 0;
        }else{
            total = combinat(n, 2);
            comfac = 0;
            for(i = 0; i < n; i++){
                scanf("%d", &num[i]);
            }
            for(i = 0; i < n; i++){
                for(j = 0; j < n; j++){
                    if(j <= i){
                        continue;
                    }else{
                        if(gbc(num[i], num[j]) == 1){
                            comfac++;
                        }
                    }
                }
            }
            if(comfac == 0){
                printf("No estimate for this data set.\n");
            }else{    
                pi = sqrt(6 * (double)total / comfac);
                printf("%.6lf\n", pi);
            }
        }
    }
    
    return 0;
}                

int combinat(int m, int n)
{
    int i, j;
    int mat[100][100];
    if(n == 0 || m == n){
        return 1;     
    }else{
        for(j = 0; j < n; j++){
            mat[0][j] = 1;
            for(i = 1; i <= m-n; i++){
                if(j == 0){
                    mat[i][j] = i+1;
                }else{
                    mat[i][j] = mat[i-1][j] + mat[i][j-1];
                }
            }
        }              			
        return (mat[m-n][n-1]);
    }
}
int gbc(int a, int b)
{
    if((a == 1) || (b == 1)){
        return 1;
    }else if((a % b == 0) || (b % a == 0)){
        return 0;
    }else{
        if(a > b){
            return (gbc((a%b), b));
        }else{
            return (gbc(a, (b%a)));
        }
    }
}