Trees in a Wood. UVA 10214 欧拉函数或者容斥定理 给定a,b求 |x|<=a, |y|<=b这个范围内的所有整点不包括原点都种一棵树。求出你站在原点向四周看到的树的数量/总的树的数量的值。

/**

题目：Trees in a Wood. UVA 10214

链接：https://vjudge.net/problem/UVA-10214

题意：给定a,b求 |x|<=a, |y|<=b这个范围内的所有整点不包括原点都种一棵树。求出你站在原点向四周看到的树的数量/总的树的数量的值。

思路：

坐标轴上结果为4，其他四个象限和第一个象限看到的数量一样。所以求出x在[1,a]和y在[1,b]的x/y互质对数即可。

由于a比较小，所以枚举x，然后求每一个x与[1,b]的互质对数。

方法：

1<=y<=x； 那么phi(x)为结果。

x+1<=y<=2*x; 那么phi(x)为结果。因为gcd(x+i,x) = gcd(x,i);

2*x+1<=y<=3*x; 同理

.

.

k*x+1<=y<=b; 直接暴力枚举判断即可了

当然求x与[1,b]范围内的互质对数还可以使用容斥做法。求出x的所有素因子。

求b范围内有多少个数与x含有至少一个相同的素因子。由于会出现重复计算，所以容斥处理。

*/

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cstdio>

#include<vector>

#include<set>

#include<cmath>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int inf = 0x3f3f3f3f;

const int maxn = 2e3+;

int a, b;

int phi[maxn];

void init()

{

    for(int i = ; i < maxn; i++) phi[i] = i;

    for(int i = ; i < maxn; i+=) phi[i]/=;

    for(int i = ; i < maxn; i+=){

        if(phi[i]==i){

            for(int j = i; j < maxn; j+=i){

                phi[j] = phi[j]/i*(i-);

            }

        }

    }

}

int gcd(int a,int b)

{

    return b==?a:gcd(b,a%b);

}

ll f(int a)

{

    return 1LL**a+;

}

int main()

{

    init();

    while(scanf("%d%d",&a,&b)==&&a){

        ll ans = ;

        for(int i = ; i <= a; i++){

            ans += b/i*phi[i];

            int st = b/i*i+;

            int et = b/i*i+b%i;

            for(int j = st; j <= et; j++){

                if(gcd(i,j)==) ans++;

            }

        }

        printf("%.7lf\n",(ans*+)*1.0/(f(a)*f(b)-));

    }

    return ;

}



莫比乌斯做法：

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cstdio>

#include<vector>

#include<set>

#include<cmath>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int inf = 0x3f3f3f3f;

const int maxn = 2e3+;

int a, b;

int mu[maxn];

int prime[maxn], tot;

void init()

{

    mu[] = ;

    tot = ;

    for(int i = ; i < maxn; i++){

        if(prime[i]==){

            prime[++tot] = i;

            mu[i] = -;

        }

        for(int j = ; prime[j]*i<maxn; j++){

            prime[prime[j]*i] = ;

            if(i%prime[j]==){

                mu[prime[j]*i] = ;

                break;

            }

            mu[prime[j]*i] = -mu[i];

        }

    }

}

ll f(int a)

{

    return 1LL**a+;

}

int main()

{

    init();

    while(scanf("%d%d",&a,&b)==&&a){

        ll ans = ;

        /*for(int i = 1; i <= a; i++){

            ans += b/i*phi[i];

            int st = b/i*i+1;

            int et = b/i*i+b%i;

            for(int j = st; j <= et; j++){

                if(gcd(i,j)==1) ans++;

            }

        }*/

        int mis = min(a,b);

        for(int i = ; i <= mis; i++){

            ans += mu[i]*1LL*(a/i)*(b/i);

        }

        printf("%.7lf\n",(ans*+)*1.0/(f(a)*f(b)-));

    }

    return ;

}