3
10
2016
0

[BZOJ2301] [HAOI2011]Problem b

我做的第一道莫比乌斯反演!

照模版写的……题解复制自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;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 334

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com