UVa 10214 (莫比乌斯反演 or 欧拉函数) Trees in a Wood.

题意：

这道题和POJ 3090很相似，求|x|≤a，|y|≤b 中站在原点可见的整点的个数K，所有的整点个数为N(除去原点)，求K/N

分析：

坐标轴上有四个可见的点，因为每个象限可见的点数都是一样的，所以我们只要求出第一象限可见的点数然后×4+4，即是K。

可见的点满足gcd(x, y) = 1，于是将问题转化为x∈[1, a]， y∈[1, b]，求gcd(x, y) = 1的个数。

类比HDU 1695可以用莫比乌斯反演来做，我还写了普通的和分块加速的两份代码，交上去发现运行时间相差并不是太多。

#include <cstdio>
#include <algorithm>
typedef long long LL;

const int maxn = 2000;
int mu[maxn+10], vis[maxn+10], prime[maxn];

void Mobius()
{
    mu[1] = 1;
    int cnt = 0;
    for(int i = 2; i <= maxn; ++i)
    {
        if(!vis[i])
        {
            mu[i] = -1;
            prime[cnt++] = i;
        }
        for(int j = 0; j < cnt && (LL)i*prime[j] <= maxn; ++j)
        {
            vis[i*prime[j]] = 1;
            if(i % prime[j] != 0) mu[i*prime[j]] = -mu[i];
            else
            {
                mu[i*prime[j]] = 0;
                break;
            }
        }
    }
    //计算前缀和，用于分块加速
    for(int i = 2; i <= 2015; ++i) mu[i] += mu[i-1];

}

int main()
{
    Mobius();
    int a, b;
    while(scanf("%d%d", &a, &b) == 2)
    {
        if(a == 0 && b == 0) break;
        LL K = 0, N = (LL)(a*2+1) * (b*2+1) - 1;
        if(a > b) std::swap(a, b);
        for(int i = 1, j; i <= a; i = j + 1)
        {
            j = std::min(a/(a/i), b/(b/i));
            K += (LL)(mu[j] - mu[i-1]) * (a/i) * (b/i);
        }
        //for(int i = 1; i <= a; ++i) K += (LL) mu[i] * (a/i) * (b/i);
        K = (K+1)*4;

        printf("%.7f
", (double) K / N);
    }

    return 0;
}

也可以按照紫书上的思路求欧拉函数，因为a的范围比较小，所以可以逐列统计。不过这个方法要比上面的莫比乌斯反演慢得多，试验了下，不管是打表还是单独计算时间都差不多

#include <cstdio>
#include <cmath>
typedef long long LL;

int phi(int n)
{
    int m = sqrt(n + 0.5);
    int ans = n;
    for(int i = 2; i <= m; ++i) if(n % i == 0)
    {
        ans = ans / i * (i-1);
        while(n % i == 0) n /= i;
    }
    if(n > 1) ans = ans / n * (n-1);
    return ans;
}

int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a%b);
}

int main()
{
    int a, b;
    while(scanf("%d%d", &a, &b) == 2 && a)
    {
        LL N = (LL)(a*2+1) * (b*2+1) - 1;
        LL K = 0;
        for(int x = 1; x <= a; ++x)
        {
            int k = b / x;
            K += phi(x) * k;
            for(int y = k*x+1; y <= b; y++)
                if(gcd(x, y) == 1) K++;
        }
        K = (K+1)*4;
        printf("%.7f
", (double)K / N);
    }

    return 0;
}