ZeroJudge 解題筆記：c087. 00412 - Pi

作者：王一哲
日期：2026年2月23日


ZeroJudge 題目連結：c087. 00412 - Pi

解題想法

如果測資提供 $n$ 個數字，所有的數對共有 $$ tot = C_n^2 = \frac{n(n-1)}{2} $$ 如果其中有 $cnt$ 組互質，則 $$ \frac{6}{\pi^2} = \frac{cnt}{tot} ~\Rightarrow~ \pi = \sqrt{\frac{6 \times tot}{cnt}} $$

Python 程式碼

用 itertools.combinations 産生數對組合，使用時間約為 7 ms，記憶體約為 2.9 MB，通過測試。

import sys, itertools, math

for line in sys.stdin:
    n = int(line)
    if n == 0: break
    nums = [int(sys.stdin.readline()) for _ in range(n)]
    cnt, tot = 0, n*(n-1)//2
    for a, b in itertools.combinations(nums, 2):
        if math.gcd(a, b) == 1: cnt += 1
    if cnt == 0:
        print("No estimate for this data set.")
    else:
        print(f"{(6*tot/cnt)**0.5:.6f}")

用遞迴枚舉所有的數對組合，使用時間約為 7 ms，記憶體約為 2.9 MB，通過測試。

import sys, math

def comb(nums, arr, cnt):
    if len(arr) == 2:
        if math.gcd(*arr) == 1: return cnt+1
        return cnt
    for i in range(len(nums)):
        arr.append(nums[i])
        cnt = comb(nums[i+1:], arr, cnt)
        arr.pop()
    return cnt

for line in sys.stdin:
    n = int(line)
    if n == 0: break
    nums = [int(sys.stdin.readline()) for _ in range(n)]
    tot = n*(n-1)//2
    cnt = comb(nums, [], 0)
    if cnt == 0:
        print("No estimate for this data set.")
    else:
        print(f"{(6*tot/cnt)**0.5:.6f}")

C++ 程式碼

使用時間約為 1 ms，記憶體約為 280 kB，通過測試。

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int comb(vector<int>&nums, vector<int>& arr, int cnt) {
    if (arr.size() == 2) {
        if (__gcd(arr[0], arr[1]) == 1) return cnt+1;
        return cnt;
    }
    for(int i=0; i<(int)nums.size(); i++) {
        arr.push_back(nums[i]);
        vector<int> tmp (nums.begin()+i+1, nums.end());
        cnt = comb(tmp, arr, cnt);
        arr.pop_back();
    }
    return cnt;
}

int main() {
    int n;
    while(scanf("%d", &n) != EOF && n != 0) {
        vector<int> nums (n), arr;
        for(int i=0; i<n; i++) scanf("%d", &nums[i]);
        int tot = n*(n-1)/2, cnt = comb(nums, arr, 0);
        if (cnt == 0) puts("No estimate for this data set.");
        else printf("%.6f\n", sqrt(6.0*tot/cnt));
    }
    return 0;
}