Coprime Integers Gym – 101982B(莫比乌斯-欧拉筛+容斥)

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

题目大意:两个集合a-b和c-d问其中有多少对数gcd==1

解题思路:一开始就想用素数筛来容斥,但是不管怎么该不是多了点就是少了点,怎么都对不了

后来还是看了大佬的代码勉强理解

 

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
bool vis[10000010];
int mu[10000010],pri[10000010];
int cnt;

void init()
{
    mu[1]=1;
    for(int i=2;i<=10000000;i++)
    {
        if(!vis[i])
        {
            mu[i]=-1;//素数都是要减掉得
            pri[cnt++]=i;
        }
        int d;
        for(int j=0;j<cnt&&i*pri[j]<=10000000;j++)
        {
            d=i*pri[j];
            vis[d]=1;
            if(i%pri[j]==0)
            {
                mu[d]=0;//保证每个数只被计算一次
                break;
            }
            else
            {
                mu[d]=-mu[i];
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    long long ans=0;
    init();
    for(int i=1;i<=b&&i<=d;i++)
    {
        if(mu[i])
        {
            //cout<<i<<" "<<mu[i]<<endl; //帮助理解
            ans+=(long long)mu[i]*(b/i-(a-1)/i)*(d/i-(c-1)/i);
            //mu[i]控制加减, 后面的是以i为公共因子的数对的个数
            //当i等于1的时候把所有的情况都加上了
            //这样的话减去2,3,等素数的倍数的数对数
            //但是比如6这样的既能被2整除又能被3整除的会多减
            //所以要让mu[2],mu[3]=-1,mu[6]=1
            //详见上面的素数筛
        }
    }
    cout<<ans<<endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注