UVa412

題目

http://domen111.github.io/UVa-Easy-Viewer/?412

給一個集合 $S$ ，從中任意取兩數 $p, q$

其中該集合所有 $p, q$ 對數記作 $A$， $p, q$ 互質的數量記作 $B$

求 $\sqrt{6*\frac{A}{B}}$ 四捨五入到小數點後第 $6$ 位

想法

這裡可以用很暴力的作法完成他

如果兩個數互質，那兩者的最大公因數一定是 $1$

那麼接下來暴力去看看每一組是不是互質，記錄下來即可

Code

//By Koios1143
#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
int gcd(int n, int m){
	if(n%m == 0){
		return m;
	}
	return gcd(m, n%m);
}
int main(){
	int n;
	while(cin>>n && n){
		int arr[55];
		for(int i=0 ; i<n ; i++){
			cin>>arr[i];
		}
		int a=0,b=0;
		for(int i=0 ; i<n ; i++){
			for(int j=i+1 ; j<n ; j++){
				a++;
				if(gcd(arr[i], arr[j]) == 1)
					b++;
			}
		}
		if(b==0)
			cout<<"No estimate for this data set.\n";
		else
			cout<<fixed<<setprecision(6)<<sqrt((double)(a*6.0/b))<<"\n";
	}
	return 0;
}

時間複雜度分析

每筆測資輸入時間複雜度為 $O(n)$

每筆測資窮舉時間複雜度約為 $O(n^2{log{min(arr[i], arr[j])}})$