UVa 412 Pi

题目描述

题目基于数论中的一个定理：从一个大集合中随机选取两个正整数，它们互质（最大公约数为111）的概率为6/π26 / \pi^26/π2。给定一个包含NNN个正整数的集合，计算其中所有无序对中互质对的比例，利用上述公式反推出π\piπ的估计值。

输入格式

输入包含多组数据。每组数据格式如下：

• 第一行一个正整数NNN（1<N<501 < N < 501<N<50），表示集合中整数的个数。
• 接下来NNN行，每行一个正整数（大于000且小于327683276832768）。
• N=0N = 0N=0表示输入结束。

输出格式

对于每组数据：

• 如果存在至少一对互质的数，则输出π\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×totalPairscoprimePairs=3N(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互质。
• 否则，不互质。

由于N<50N < 50N<50，总对数不超过122512251225，直接枚举所有对并计算gcd⁡\gcdgcd即可。

边界情况

如果coprimePairs=0\textit{coprimePairs} = 0coprimePairs=0，则公式中分母为零，无法计算估计值，此时输出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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intgcd(inta,intb){intt;while(a%b)t=a,a=b,b=t%b;returnb;}intmain(intargc,char*argv[]){ios::sync_with_stdio(false);intn;while(cin>>n,n){vector<int>number(n);for(inti=0;i<n;i++)cin>>number[i];intcounter=0;for(inti=0;i<n;i++)for(intj=i+1;j<n;j++)if(gcd(number[i],number[j])==1)counter++;if(counter==0)cout<<"No estimate for this data set."<<endl;else{longdoublepi=sqrt(3.0*n*(n-1)/counter);cout<<fixed<<setprecision(6)<<pi<<endl;}}return0;}