【題解】UVa 10214 【Trees in a Wood.】

这题有两种方法:
第一种:来自刘汝佳的算法竞赛入门经典第二版的339页,介绍了用欧拉函数的解法,然而我并不会qwq,所以只有第二种方法。

第二种:
莫比乌斯反演:

其实这题很像[https://www.luogu.org/problemnew/show/P2158](P2158 仪仗队),只是四个象限而已,不过有很多坑点。

这题数据灰常大(这里不是指会超时(如果不是的暴力的呼话)),2000 * 2000000 会爆int,所以得开long long。然后记得转换成浮点数相除。

其实题意很简单,就是求:

其中n = a,m = b,k = 1,然后把答案乘上4再加4;

而求上式便是莫比乌斯反演(懵逼钨丝反演)的一大应用

设f(k)为gcd(i,j) = k的个数,g(k)为满足k | gcd(i,j)的对数,

由反演有:

其中mu(x)为莫比乌斯函数,可用线性筛求出

代码如下:(注意:下面的代码中使用了分块的思想(公共乘积优化),预处理了前缀和(我不打算在题解里讲了,有兴趣的去看我的LuoGu博客))

#include<cstdio>
#include<algorithm>

const int L = 40000 + 6;

typedef long long Long;//简化代码

int primes[L],mu[L],num,sum[L];
bool isPrime[L];

//线性筛莫比乌斯函数,就是线筛加了点东西
void sieve(int len){
    std::fill(isPrime,isPrime + len + 1,true);

    mu[1] = 1;//由定义mu(1)=1
    num = 0;

    for(int i = 2;i < len;++i){
        if(isPrime[i]){
            primes[num++] = i;
            mu[i] = -1;
        }
        static int d;
        for(int j = 0;j < num && (d = i * primes[j]) < len;++j){
            isPrime[d] = false;
            if(i % primes[j] == 0){
                mu[d] = 0;
                break;
            }else{
                mu[d] = -mu[i];
            }
        }
    }

    //处理前缀和,用于分块
    sum[0] = 0;
    for(int i = 1;i <= L;i++){
        sum[i] = sum[i - 1] + mu[i];
    }
}

//求解f(x),n,m是上界,d = k
Long f(int n, int m, int d) {
    if(n > m){
        std::swap(n, m);
    }
    Long ans = 0;
    n /= d, m /= d;
    for(int i = 1, last = 1; i <= n; i = last + 1){
        last = std::min(n / (n / i), m / (m / i));
        ans += (Long)(sum[last] - sum[i - 1]) * (n / i) * (m / i);
    }

    return ans * 4 + 4;//上述代码求出的是一个象限,总数需要*4 + 4个坐标轴上的4个点
}

int main(){
    sieve(L);//记得调用,我每次都忘qwq

    int a,b;
    while(scanf("%d %d",&a,&b) == 2 && a){
        Long K = f(a,b,1);
        Long N = (Long)(a * 2 + 1) * (b * 2 + 1) - 1;//这里一定记得赋值号右边也要强制类型转换

        printf("%.7lf\n",(double)K / (double)N);
    }

    return 0;
}