UVa 412 Pi

题目描述题目基于数论中的一个定理从一个大集合中随机选取两个正整数它们互质最大公约数为111的概率为6/π26 / \pi^26/π2。给定一个包含NNN个正整数的集合计算其中所有无序对中互质对的比例利用上述公式反推出π\piπ的估计值。输入格式输入包含多组数据。每组数据格式如下第一行一个正整数NNN1N501 N 501N50表示集合中整数的个数。接下来NNN行每行一个正整数大于000且小于327683276832768。N0N 0N0表示输入结束。输出格式对于每组数据如果存在至少一对互质的数则输出π\piπ的估计值保留666位小数。如果没有互质的数对则输出No estimate for this data set.。样例输入5 2 3 4 5 6 2 13 39 0输出3.162278 No estimate for this data set.题目分析本题的核心是计算给定集合中所有无序对的最大公约数统计互质对的数量然后利用概率公式反推π\piπ。公式推导设总共有NNN个数则无序对的总数为totalPairs(N2)N(N−1)2 \textit{totalPairs} \binom{N}{2} \frac{N(N-1)}{2}totalPairs(2N​)2N(N−1)​设互质对的数量为coprimePairs\textit{coprimePairs}coprimePairs则互质对的比例为coprimePairstotalPairs \frac{\textit{coprimePairs}}{\textit{totalPairs}}totalPairscoprimePairs​根据定理该比例应等于6/π26 / \pi^26/π2因此6π2≈coprimePairstotalPairs \frac{6}{\pi^2} \approx \frac{\textit{coprimePairs}}{\textit{totalPairs}}π26​≈totalPairscoprimePairs​π2≈6×totalPairscoprimePairs3N(N−1)coprimePairs \pi^2 \approx \frac{6 \times \textit{totalPairs}}{\textit{coprimePairs}} \frac{3N(N-1)}{\textit{coprimePairs}}π2≈coprimePairs6×totalPairs​coprimePairs3N(N−1)​π≈3N(N−1)coprimePairs \pi \approx \sqrt{\frac{3N(N-1)}{\textit{coprimePairs}}}π≈coprimePairs3N(N−1)​​互质对判定对于每对数(a,b)(a, b)(a,b)使用欧几里得算法计算其最大公约数若gcd⁡(a,b)1\gcd(a, b) 1gcd(a,b)1则aaa和bbb互质。否则不互质。由于N50N 50N50总对数不超过122512251225直接枚举所有对并计算gcd⁡\gcdgcd即可。边界情况如果coprimePairs0\textit{coprimePairs} 0coprimePairs0则公式中分母为零无法计算估计值此时输出No estimate for this data set.。精度要求输出需要保留666位小数使用浮点数运算时应注意精度。π\piπ的估计值使用double或long double类型计算即可。复杂度分析每组数据需要计算O(N2)O(N^2)O(N2)次gcd⁡\gcdgcd每次gcd⁡\gcdgcd的时间复杂度为O(log⁡max⁡(a,b))O(\log \max(a, b))O(logmax(a,b))。N≤50N \le 50N≤50完全可接受。代码实现// Pi// UVa ID: 412// Verdict: Accepted// Submission Date: 2016-07-14// UVa Run Time: 0.060s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intgcd(inta,intb){intt;while(a%b)ta,ab,bt%b;returnb;}intmain(intargc,char*argv[]){ios::sync_with_stdio(false);intn;while(cinn,n){vectorintnumber(n);for(inti0;in;i)cinnumber[i];intcounter0;for(inti0;in;i)for(intji1;jn;j)if(gcd(number[i],number[j])1)counter;if(counter0)coutNo estimate for this data set.endl;else{longdoublepisqrt(3.0*n*(n-1)/counter);coutfixedsetprecision(6)piendl;}}return0;}