BZOJ2301/LG2522 「HAOI2011」Problem B 莫比乌斯反演 数论分块
问题描述
积性函数
若函数 (f(x)) 满足对于任意两个最大公约数为 (1) 的数 (m,n) ,有 (f(mn)=f(m) imes f(n)),则称 (f(x)) 为积性函数。
狄利克雷卷积和莫比乌斯函数
今天 zzk 神仙讲了一下狄利克雷卷积、数论分块和莫比乌斯反演。
几个数论函数
以上这几个数论函数都是积性函数。
狄利克雷卷积
有函数 (f(x),g(x)) , 若有函数 (h(x)=sumlimits_{d|x}{f(d)g(frac{x}{d})}) ,则称 (h(x)) 是 (f(x),g(x)) 的卷积。
记作 (h(x)=f(x)*g(x))
狄利克雷卷积有如下性质:
-
交换律,即 (f*g=g*f)
-
结合律,即 ((a*b)*c=a*(b*c))
-
若 (f,g) 都是积性函数,则 (f*g) 也是积性函数,即 (f*g(mn)=f*g(m) imes f*g(n)((n,m)=1))
(varepsilon)
若 (f*g = varepsilon) ,则 (f) 与 (g) 互为逆
莫比乌斯函数
(mu(x))代表莫比乌斯函数。
对 (x) 应有质数唯一分解定理,将 (x) 表示为 (x=prod_{i=1}^{k} p_i^{c_i}) ,则有
莫比乌斯函数是一个积性函数,即对于满足 ((x,y)=1) 的 (x,y) ,有 (mu(xy)=mu(x) imes mu(y))
有重要性质 (sumlimits_{d|x}{mu(d)}=varepsilon=egin{cases}0&x eq 1\1&x=1end{cases})
莫比乌斯反演
套式子:
用狄利克雷卷积来解释,就是 (f=g*1,g=f*mu)
数论分块
简单问题
数论分块一般的问题是求 (sum_{d=1}^n{lfloor frac{n}{d} floor})
考虑分块思想,把 (lfloor frac{n}{d} floor) 数值相同的划分为一块求。
于是可以得到以下代码:
(1)
题解
题意是要求 (sumlimits_{i=a}^{b}{sumlimits_{j=c}^{d}{[(i,j)==k]}})
显然可以通过差分,将问题转化为求 (sumlimits_{i=1}^{n}{sumlimits_{j=1}^{m}{[(i,j)==k]}})
可以通过在两边同时除去 (k) ,得到
考虑最大公约数为 (1) 的要求,可以想到 ([(i,j)==1]) 的条件可以直接改为 (varepsilon((i,j)))
又因为 (varepsilon((i,j))=sumlimits_{d|(i,j)}{mu(d)}) ,所以式子转化为
对 (sum) 进行变换,得到
(mathrm{Code})
#include<bits/stdc++.h>
using namespace std;
const int maxn=50000;
int T;
void Init(void){
scanf("%d",&T);
}
int p[maxn+7],pr[maxn+7],miu[maxn+7],s[maxn+7];
int tot;
void preprocess(){
miu[1]=1;
for(int i=2;i<=maxn;i++){
if(!p[i]) p[i]=i,pr[++tot]=i,miu[i]=-1;
for(int j=1;j<=tot;j++){
if(i*pr[j]>maxn||p[i]<pr[j]) break;
p[i*pr[j]]=pr[j];
if(i%pr[j]) miu[i*pr[j]]=-miu[i];
else miu[i*pr[j]]=0;
}
}
for(int i=1;i<=maxn;i++) s[i]=s[i-1]+miu[i];
}
int calc(int x,int y){
if(x>y) swap(x,y);
if(x==0||y==0) return 0;
int res(0);
for(int l=1,r;l<=x;l=r+1){
r=min(x/(x/l),y/(y/l));
res+=(s[r]-s[l-1])*(x/l)*(y/l);
}
return res;
}
void Work(void){
preprocess();
while(T--){
int a,b,c,d,k;
scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
--a,--c;
printf("%d
",calc(b/k,d/k)+calc(a/k,c/k)-calc(a/k,d/k)-calc(b/k,c/k));
}
}
int main(){
Init();
Work();
return 0;
}