BZOJ2301/LG2522 「HAOI2011」Problem B 莫比乌斯反演数论分块

问题描述

BZOJ2301

LG2522

积性函数

若函数 \(f(x)\) 满足对于任意两个最大公约数为 \(1\) 的数 \(m,n\) ，有 \(f(mn)=f(m) \times f(n)\)，则称 \(f(x)\) 为积性函数。

狄利克雷卷积和莫比乌斯函数

今天 zzk 神仙讲了一下狄利克雷卷积、数论分块和莫比乌斯反演。

几个数论函数

\[1(x)=1
\]

\[id(x)=x
\]

\[id^k(x)=x^k
\]

\[\varepsilon(x)=\begin{cases}1&x=1\\0&x\neq1\end{cases}
\]

以上这几个数论函数都是积性函数。

狄利克雷卷积

有函数 \(f(x),g(x)\) ，若有函数 \(h(x)=\sum\limits_{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) \times 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}\) ，则有

\[\mu(x)=\begin{cases}0&\exists c_i \ge 2\\(-1)^{k}&\forall c_i=1\end{cases}
\]

莫比乌斯函数是一个积性函数，即对于满足 \((x,y)=1\) 的 \(x,y\) ，有 \(\mu(xy)=\mu(x) \times \mu(y)\)

有重要性质 \(\sum\limits_{d|x}{\mu(d)}=\varepsilon=\begin{cases}0&x \neq 1\\1&x=1\end{cases}\)

莫比乌斯反演

套式子：

\[f(x)=\sum\limits_{d|x}g(d) \Rightarrow g(x)=\sum\limits_{d|x}f(d)\mu(\frac{x}{d})
\]

用狄利克雷卷积来解释，就是 \(f=g*1,g=f*\mu\)

数论分块

简单问题

数论分块一般的问题是求 \(\sum_{d=1}^n{\lfloor \frac{n}{d} \rfloor}\)

考虑分块思想，把 \(\lfloor \frac{n}{d} \rfloor\) 数值相同的划分为一块求。

于是可以得到以下代码：

稍复杂问题 \(1\)

题解

题意是要求 \(\sum\limits_{i=a}^{b}{\sum\limits_{j=c}^{d}{[(i,j)==k]}}\)

显然可以通过差分，将问题转化为求 \(\sum\limits_{i=1}^{n}{\sum\limits_{j=1}^{m}{[(i,j)==k]}}\)

可以通过在两边同时除去 \(k\) ，得到

\[\sum\limits_{i=1}^{\frac{n}{k}}{\sum\limits_{j=1}^{\frac{m}{k}}{[(i,j)==1]}}
\]

考虑最大公约数为 \(1\) 的要求，可以想到 \([(i,j)==1]\) 的条件可以直接改为 \(\varepsilon((i,j))\)

又因为 \(\varepsilon((i,j))=\sum\limits_{d|(i,j)}{\mu(d)}\) ，所以式子转化为

\[\sum\limits_{i=1}^{\frac{n}{k}}{\sum\limits_{j=1}^{\frac{m}{k}}{\sum\limits_{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\n",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;

}

巴特西

BZOJ2301/LG2522 「HAOI2011」Problem B 莫比乌斯反演数论分块

问题描述

积性函数

狄利克雷卷积和莫比乌斯函数

几个数论函数

狄利克雷卷积

单位元 \(\varepsilon\)

莫比乌斯函数

莫比乌斯反演

数论分块

简单问题

稍复杂问题 \(1\)

题解

\(\mathrm{Code}\)

最新文章

热门文章

巴特西

BZOJ2301/LG2522 「HAOI2011」Problem B 莫比乌斯反演 数论分块

问题描述

积性函数

狄利克雷卷积和莫比乌斯函数

几个数论函数

狄利克雷卷积

单位元 \(\varepsilon\)

莫比乌斯函数

莫比乌斯反演

数论分块

简单问题

稍复杂问题 \(1\)

题解

\(\mathrm{Code}\)

最新文章

热门文章

BZOJ2301/LG2522 「HAOI2011」Problem B 莫比乌斯反演数论分块