题目链接：https://cn.vjudge.net/problem/HDU-1695#author=541607120101

感觉讲的很好的一个博客：https://www.cnblogs.com/peng-ym/p/8647856.html

今天刚开始学莫比乌斯反演，先据我所了解的说一下。

首先是莫比乌斯函数。

1，mu(x).当x为1时，mu（1）等于1。

2，当x为素数时，mu（x）=-1。

3，当x能唯一分解成多个不同的素数相乘的时候（不能有重复的素数）mu（x）=（-1）的k次方，k代表的是素数的个数。

4，当x不能被唯一的分解成多个素数相乘的时候，也就是他的因子中存在重复的素数，这个时候，mu（x）=0.

然后是一个等式 (d是n的因子).

然后就是两个等式(等我学会证明就回来补~)

然后对于当前这个题,选择(1,b),(1,d) 中满足gcd(x,y)==k的对数,(1<=x<=b),(1<=y<=d) .

也就是说 gcd(x/k,y.k)==1满足的对数.

然后再开始分析一波:

我们令f(k)为满足(a,b),(c,d)中的gcd为k的对数.然后F(k)就是满足(a,b),(c,d)中的gcd为k的倍数的对数.

F(k)就等于(b/k)*(d/k).

所以说,这个题就转换为了求满足的总和

但是要注意去重.我们一开始定义的是ans=f(1)( (1<=x<=b) &&(1<=y<=c) )中的解,但是很明显,(1.c)包含(1,b),所以这一块会有重复的计算( (1<=x<=b)&&(1<=x<=b) ),并且(t1,t2)和(t2,t1)在(1,b)这块区域,是应当被看做一组的,所以最终结果应该是

ans=f ( (1,b) , (1,c) )-f ( (1,b) , (1,b) ) / 2.

AC代码:

#include<iostream>

#include<cmath>

#include<string>

#include<algorithm>

#include<cstring>

#include<stdio.h>

using namespace std;

# define ll long long

# define inf 0x3f3f3f3f

const int maxn =100000+100;

# define ll long long

ll mu[maxn];

ll vis[maxn];

ll prim[maxn];

void Get_mu(ll n)

{

    mu[1]=1;

    int cnt=0;

    for(ll i=2; i<n; i++)

    {

        if(!vis[i])

        {

            prim[cnt++]=i;

            mu[i]=-1;

        }

        for(ll j=0; j<cnt; j++)

        {

            ll k=i*prim[j];

            if(k>n)break;

            vis[k]=1;

            if(i%prim[j])

            {

                mu[k]=-mu[i];

            }

            else

            {

                mu[k]=0;

                break;

            }

        }

    }

}

int main()

{

    Get_mu(maxn);

    ll t;

    ll Case=0;

    scanf("%lld",&t);

    while(t--)

    {

        ll a,b,c,d,k;

        scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&k);

        if(k==0)

        {

            printf("Case %lld: 0\n",++Case);

            continue;

        }

        b/=k;

        d/=k;

        ll ans=0,res=0;

        ll minn=min(b,d);

        for(ll i=1; i<=minn; i++)

        {

            ans+=mu[i]*(b/i)*(d/i);

            res+=mu[i]*(minn/i)*(minn/i);

        }

        //  cout<<ans<<" "<<res<<endl;

        printf("Case %lld: %lld\n",++Case,ans-res/2);

    }

    return 0;

}