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

题目链接: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;

}

巴特西

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

最新文章

热门文章

巴特西

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

最新文章

热门文章

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