[TIOJ] 1005. 圓周率問題

題目連結:http://tioj.infor.org/problems/1005

---

就按照題目做，直接$O(n^2)$把所有組合跑過一遍做gcd，然後算就好，但要記得處理一下浮點數誤差

#include <stdio.h>
#include <math.h>
int gcd(int a, int b){
        int t;
        if(b>a){
                t = b;
                b = a;
                a = t;
        }
        int last;
        do{
                a %= b;
                last = a;
                t = b;
                b = a;
                a = t;
        }while(last!=0);
        return a;
}

void read(int sum){
        if(sum!=0){
                int a = 0, count = 0, all = 0;
                int temp[50];
                for(int i = 0;i<sum;i++){
                        scanf("%d",&a);
                        temp[i] = a;
                }
                for(int i = 0;i<sum;i++){
                        for(int j = i+1;j<sum;j++){
                                all++;
                                if(gcd(temp[i], temp[j])==1){
                                        count++;
                                }
                        }
                }
                if(count!=0)
                        printf("%.6f\n", (float)sqrt((all * 6.0 / count)));
                else
                        printf("No estimate for this data set.\n");
        }
}
int main(){
        int s;
        do{
                scanf("%d",&s);
                read(s);
        }while(s!=0);
        return 0;
}