[BZOJ2301/Luogu2522][HAOI2011]Problem b(莫比乌斯反演,容斥原理,数论分块)

发布于 2018-01-17  45 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2301/Luogu2522][HAOI2011]Problem b(莫比乌斯反演,容斥原理,数论分块)

Description

对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd(x,y)函数为x和y的最大公约数。

Http

BZOJ
Luogu

Tag

莫比乌斯反演,容斥原理,数论分块

题目大意

求\[\sum_{i=a}^{b} \sum_{j=c}^{d} [gcd(i,j)==K]\]

解决思路

先考虑求解\[Ans=\sum_{i=1}^{n} \sum_{j=1}^{m} gcd(i,j)==K\]
这个式子可以化成\[Ans=\sum_{i=1}^{n/K} \sum_{j=1}^{m/K} [gcd(i,j)==1]\]
由莫比乌斯反演可得(具体推导可以参考这里
\[Ans=\sum_{i=1}^{n/K} \mu(i) \lfloor \frac{n/K}{i} \rfloor * \lfloor \frac{m/K}{i} \rfloor\]
那么再考虑\(i\)从\(a\)开始,\(j\)从\(c\)开始。可以像求二维前缀和一样简单容斥一下,设\[Calc(n,m)=\sum_{i=1}^{n} \sum_{j=1}^{m} [gcd(i,j)==1]\],那么最后的答案就是
\[Ans=Calc(b,d)-Calc(a-1,d)-Calc(b,c-1)+Calc(a-1,c-1)\]

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxNum=50010;
const int inf=2147483647;

int Mu[maxNum];
int Musum[maxNum];
int pricnt=0,Prime[maxNum];
bool notprime[maxNum];

void GetMu();//线性筛求mu
int Calc(int n,int m);//计算子问题

int main()
{
    GetMu();
    int T;scanf("%d",&T);
    while (T--)
    {
        int a,b,c,d,K;scanf("%d%d%d%d%d",&a,&b,&c,&d,&K);
        printf("%d\n",Calc(b/K,d/K)-Calc((a-1)/K,d/K)-Calc(b/K,(c-1)/K)+Calc((a-1)/K,(c-1)/K));
    }
    return 0;
}

void GetMu()
{
    notprime[1]=1;Mu[1]=1;
    for (int i=2;i<maxNum;i++)
    {
        if (notprime[i]==0) Prime[++pricnt]=i,Mu[i]=-1;
        for (int j=1;(j<=pricnt)&&((ll)i*(ll)Prime[j])<maxNum;j++)
        {
            notprime[i*Prime[j]]=1;
            if (i%Prime[j]==0) break;
            Mu[i*Prime[j]]=-Mu[i];
        }
    }
    for (int i=1;i<maxNum;i++) Musum[i]=Musum[i-1]+Mu[i];
    return;
}

int Calc(int n,int m)
{
    int ret=0;if (n>m) swap(n,m);
    for (int i=1,last;i<=n;i=last+1)
    {
        last=min(n/(n/i),m/(m/i));
        ret=ret+(Musum[last]-Musum[i-1])*(n/i)*(m/i);
    }
    return ret;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2301/Luogu2522][HAOI2011]Problem b(莫比乌斯反演,容斥原理,数论分块)


HNCJ OIer 一枚