我做的第一道莫比乌斯反演！
照模版写的……题解复制自ACDreamer
-----------------------------------------------------------
我们知道莫比乌斯反演的一般描述为：
其实它还有另一种描述，本题也是用到这种。那就是：
好了，到了这里，我们开始进入正题。。。
对于本题，我们设
那么，很显然
反演后得到
--------------------------------------
然后我们对于莫比乌斯函数统计前缀和然后加一加就好了啦！
详细请看代码
#include<cstdio>
#include<algorithm>
using namespace std;
int n,a,b,c,d,k,tab[50005],cnt,prime[50005],mu[50005],sum[50005];
void Mobius(int num){
mu[1]=1;
for(int i=2;i<=num;i++){
if(!tab[i]){
prime[++cnt]=i;
mu[i]=-1;
}
for(int j=1;j<=cnt && i*prime[j]<=num;j++){
tab[i*prime[j]]=1;
if(i%prime[j])mu[i*prime[j]]=-mu[i];
else {mu[i*prime[j]]=0;break;}
}
}
}
int Solve(int x,int y){
int ans=0,cs=0;
if(x>y)swap(x,y);
for(int i=1;i<=x;i=cs+1){
cs=min(x/(x/i),y/(y/i));
ans+=(sum[cs]-sum[i-1])*(x/i)*(y/i);
}
return ans;
}
int main(){
freopen("2301.in","r",stdin);
freopen("2301.out","w",stdout);
scanf("%d",&n);
Mobius(50000);
for(int i=1;i<=50000;i++)sum[i]=sum[i-1]+mu[i];
while(n--){
scanf("%d %d %d %d %d",&a,&b,&c,&d,&k);
printf("%d\n",Solve(b/k,d/k)-Solve((a-1)/k,d/k)-Solve(b/k,(c-1)/k)+Solve((a-1)/k,(c-1)/k));
}
return 0;
}
评论 (0)
