莫比乌斯反演第二弹 入门 Coprime Integers Gym – 101982B

题目链接:https://cn.vjudge.net/problem/Gym-101982B

题目大意: 给你(a,b)和(c,d)这两个区间,然后问你这两个区间中互素的对数是多少.

具体思路:和我上一篇写莫比乌斯入门的博客的思路一样,不过就是加了下限,原来的那一篇的下限是1,现在这一篇的下限是题目给的数.所以这一块就需要考虑到去重.

第一步,我们首先确定一个较小的区间,假设让第一个区间是上限最小的,然后我们当前就有两个区间(a,b)和(c,d) 此时(b<d).

我们首先算(1,b)和(1,d)中满足情况的对数.然后这中间就会有一部分不符合条件的,( 1 , a )和 (1, d )这块的不符合, (1,c)和 (1,d)这个区域也是多算上的,但是,如果讲这两部分都给删掉的话,那么 (1,a)和(1,c)这个区域就会被删去两遍,所以需要再加上一遍.

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 =10000000+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);
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    ll ans=0;
    if(b>d){
    swap(a,c);
    swap(b,d);
    }// 注意如果交换的都需要交换.
    for(int i=1; i<=b; i++)
    {
        ans+=mu[i]*(b/i)*(d/i);
    }
    for(int i=1; i<=a-1; i++)
    {
        ans-=mu[i]*((a-1)/i)*(d/i);
    }
    for(int i=1; i<=c-1; i++)
    {
        ans-=mu[i]*((c-1)/i)*(b/i);
    }
    int temp=min(a,c);
    for(int i=1; i<=temp-1; i++)
    {
        ans+=mu[i]*((a-1)/i)*((c-1)/i);
    }
    cout<<ans<<endl;
    return 0;
}