您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

UVA 10214：Trees in a Wood——歐拉 φ 函數計算可見樹木

編輯：關於C++

題目描述

原點種樹，座標 (x,y) 滿足 |x|≤a, |y|≤b（不含原點）。從原點看，樹被遮擋當且僅當 gcd(|x|,|y|) > 1。求可見樹木比例 K/N，精度 1e-7。

數學轉化

利用對稱性，只算第一象限（x>0,y>0）再 ×4，加上 4 棵軸上樹
固定 x，y 從 1 到 b 中與 x 互質的個數
gcd(y, x) = gcd(y+x, x) = gcd(y+kx, x) ⇒ 每 x 個 y 中互質個數為 φ(x)

計算公式

K = 4 + 4 × Σ_{x=1..a} [ (b/x) × φ(x) + count(y=1..b%x, gcd(y,x)=1) ]
N = (2a+1)(2b+1) - 1

預處理 φ(1..2000) + gcd 表

int phi[2005], gcd[2005][2005];
void init() {
    phi[1] = 1;
    for (int i = 2; i <= 2000; ++i)
        if (!phi[i])
            for (int j = i; j <= 2000; j += i)
                if (!phi[j]) phi[j] = j, phi[j] = phi[j] / i * (i-1);
    for (int i = 1; i <= 2000; ++i)
        for (int j = 1; j <= 2000; ++j)
            gcd[i][j] = gcd[j][i] = __gcd(i,j);
}

主循環

while (scanf("%d%d", &a, &b), a||b) {
    if (a > b) swap(a,b);
    double K = 0;
    for (int x = 1; x <= a; ++x) {
        K += (b/x) * phi[x];
        for (int y = 1; y <= b%x; ++y)
            if (gcd[x][y] == 1) ++K;
    }
    K = K * 4 + 4;
    double N = (2.0*a+1)*(2.0*b+1) - 1;
    printf("%.7lf\n", K/N);
}