BZOJ 2301 [HAOI2011]Problem b ——莫比乌斯反演

时间:2023-03-09 09:36:13
BZOJ 2301 [HAOI2011]Problem b ——莫比乌斯反演

分成四块进行计算,这是显而易见的。(雾)

然后考虑计算$\sum_{i=1}^n|sum_{j=1}^m gcd(i,j)=k$

首先可以把n,m/=k,就变成统计&i<=n,j<=m gcd(i,j)==1 &

如果我们用卷积进行计算。gcd不好展开,我们套一个e

$\sum_{i=1}^n|sum_{j=1}^m e(gcd(i,j))$

$=\sum_{i=1}^n|sum_{j=1}^m \sum_{d \mid i,d \mid j}/mu(d) $

$=\sum_{d \mid n} \mu(d) * \lfloor n/d \rfloor * \lfloor m/d \rfloor$

然后下界函数分块即可。

然后试着莫比乌斯反演

令 F(d)表示 d|gcd(i,j) 的个数 f(d)表示 gcd(i,j)=d的个数

然后发现gcd是类似后缀和的一类东西,所以

$F(d)=\sum_{d \mid n} f(n)$

然后反演就可以得到

$f(d)=\sum_{d \mid n} F(d)*\mu( \lfloor n/d \rfloor )$

然后发现$F(d)=\lfloor n/d \rfloor * \lfloor m/d \rfloor$

喜闻乐见下界函数分块即可

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i)
#define ll long long
#define maxn 100005 int mu[maxn],pr[maxn],top=0,vis[maxn],sum[maxn]; void init()
{
mu[1]=sum[1]=1;
F(i,2,maxn-1)
{
if (!vis[i]) mu[i]=-1,pr[++top]=i,vis[i]=1;
F(j,1,top)
{
if (i*pr[j]>=maxn) break;
vis[i*pr[j]]=1;
if (i%pr[j]==0) {mu[i*pr[j]]=0;break;}
mu[i*pr[j]]=-mu[i];
}
sum[i]=sum[i-1]+mu[i];
}
} int t,a,b,c,d,k; ll cal(int n,int m,int k)
{
ll ret=0;n/=k;m/=k;if (n>m) swap(n,m);
if (n==0) return 0;
for (int i=1,last=0;i<=n;i=last+1)
{
last=min(n/(n/i),m/(m/i));
ret+=((ll)sum[last]-(ll)sum[i-1])*(n/i)*(m/i);
}
return ret;
} int main()
{
init();
scanf("%d",&t);
while (t--)
{
scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
printf("%lld\n",cal(b,d,k)-cal(a-1,d,k)-cal(b,c-1,k)+cal(a-1,c-1,k));
}
}