hdu1695+莫比乌斯反演入门

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1695
题目大意：多样例测试，每次给你5个数a, b, c, d, k;
问你a<=x<=b, c<=y<=d,(题目说每个样例a=c=1恒成立)， 有多少个(x, y)使得gcd(x, y)=k;
并且要去重（2， 3）与（3， 2）算一个

思路：拿到这道题gcd(x, y)=k即gcd(x/k, y/k)=1有多少个，很容易想到欧拉函数，在区间枚举y/k求欧拉函数和即可，但是这样x/k必须等于y/k。而这道题没有这个条件

我们看莫比乌斯反演的倍数公式

F（d）为有多少对（x,y）满足 gcd（x,y）== d 的倍数 。
f （d）为有多少对（x,y）满足 gcd（x,y）== d
这时就满足上面的公式,并且对于区间[1, x], [1, y]计算F(d)=（x/d）*(y/d);
d的取值最大为min(x, y)
例如[1, 21] ,[1, 30]
x={5, 10, 15, 20}
y={5, 10, 15, 20, 25, 30}
F(5)=（21/5）*（30/5）=24；
(5, 5), (5, 10)……………..(20, 30)
所以只要求 f(1) 即可
当然还要去重，例如区间[1, 21] ,[1, 30]，出现重复只可能在[1, 21],[1, 21], 而区间[1, 21],与[22, 30]不存在重复，所以(区间[1, 21] ,[1, 30])-(区间[1, 21],[1, 21])/2
详细题解参考：https://blog.csdn.net/lixuepeng_001/article/details/50577932

思考：莫比乌斯反演就是把问题转化成倍数关系的问题（并且倍数关系的等式），这是我做的第一道莫比乌斯反演题，领悟还不够，还要多刷题啊

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn=100005;

LL prime[maxn], mob[maxn], vis[maxn], cnt;

void mobius()//莫比乌斯函数筛
{
    memset(prime, 0, sizeof(prime));
    memset(mob, 0, sizeof(mob));
    memset(vis, 0, sizeof(vis));
    mob[1]=1;
    cnt=0;
    for(LL i=2;i<maxn;i++)
    {
        if(!vis[i])
        {
            prime[cnt++]=i;
            mob[i]=-1;
        }
        for(LL j=0;j<cnt&&i*prime[j]<maxn;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j])
                mob[i*prime[j]]=-mob[i];
            else
            {
                mob[i*prime[j]]=0;
                break;
            }
        }
    }
}

int main()
{
    mobius();
    int t;
    cin>>t;
    for(int t1=1;t1<=t;t1++)
    {
        int a, b, c, d, k;
        cin>>a>>b>>c>>d>>k;
        cout<<"Case "<<t1<<": ";
        if(k==0)//k==0特殊处理
        {
            cout<<0<<endl;
            continue;
        }
        b=b/k, d=d/k;
        LL ans1=0, ans2=0;

        for(int i=1;i<=min(b, d);i++)//总区间
        {
            ans1+=(LL)mob[i]*(b/i)*(d/i);
        }
        for(int i=1;i<=min(b, d);i++)//重复区间
        {
            ans2+=(LL)mob[i]*(min(b, d)/i)*(min(b, d)/i);
        }

        cout<<ans1-ans2/2<<endl;//去重处理
    }

    return 0;
}