【数论函数变换总结】【超长篇】【last update:2014-10-22】

现在的位置: 首页 > 综合 > 正文

RSS

【数论函数变换总结】【超长篇】【last update:2014-10-22】

2017年04月19日 ⁄ 综合 ⁄ 共 1196字 ⁄ 字号小中大 ⁄ 评论关闭

最近被好多数论题虐翻……感觉学到了不少东西,总结一下

参考文献

数论函数变换 orz kAc http://pan.baidu.com/s/1mgn4oqO

数学常识
orz drcow http://pan.baidu.com/s/1mgGA4UO

积性函数..题目
orz jcvb http://jcvb.is-programmer.com/posts/41846.html

贾志鹏线性筛
orz jzp http://wenku.baidu.com/link?url=9spLgiNU8yom2-paqarcDfsbAzLUgyYwalwv7V5K8W-lGl4qS_seaX-NlOukspGTDltU1tVhNPlBF76QKtvnDyxDxl-wL6BRxVWiWGiFipm

莫比乌斯反演是指

$g(n)=\sum_{d|n}f(d) \\~~~~~f(n)=\sum_{d|n}\mu(d)f(\frac{n}{d})$

狄利克雷卷积是指

$(f \times g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})$

所以莫比乌斯反演又可以写作

$f=g \times 1 \\~~~~~ g= \mu \times f$

顺便定义一下

$(f + g)(n)=f(n)+g(n) \\~~~~~~(f * g)(n)=f(n)*g(n)$

常见数论函数

欧拉函数

$\varphi(n)=\sum_i^n[gcd(i,n)=1]$

莫比乌斯函数

$\mu(n)=\left\{\begin{matrix} 0 \ ,if \ d>1 \ and \ d^2|n\\ (-1)^k,k=\sum_ia_i \ ,n=\prod_i p_i^{a_i} \end{matrix}\right.$

其他常见数论函数

$e(n)=[n=1]$

$id(n)=n$

$1(n)=1$

$d(n)=\sum_{d|n}1$

$\sigma (n)=\sum_{d|n}d$

常见变换

$\sum_{d|n}\varphi(d)=n ~~~~id =\varphi \times 1$

$\sum_{d|n}\mu(d)=e ~~~~e =\mu \times 1$

有了以上基础我们就来推式子了!!!

1D gcd sum

$\sum_i^n gcd(i,n) \\~=\sum_i^n\sum_{d|i,n}\varphi(d) \\~=\sum_{d|n}\varphi(d)\frac{n}{d}$

1..n中与n互质的数的个数

$\sum_i^n e(gcd(i,n)) \\~=\sum_i^n\sum_{d|i,n}\mu(d) \\~=\sum_{d|n}\mu(d)\frac{n}{d}$

2D gcd sum

$\sum_i^n\sum_j^m gcd(i,j) \\~~=\sum_i^n\sum_j^m\sum_{d|i,j}\varphi(d) \\~~=\sum_{d\leqslant n}\varphi(d)\left \lfloor \frac{n}{d} \right \rfloor\left \lfloor \frac{m}{d} \right \rfloor$

1..n和1..m中互质的数的对数

$\sum_i^n\sum_j^m e(gcd(i,j)) \\~~=\sum_i^n\sum_j^m\sum_{d|i,j}\mu(d) \\~~=\sum_{d\leqslant n}\mu(d)\left \lfloor \frac{n}{d} \right \rfloor\left \lfloor \frac{m}{d} \right \rfloor$

约数和之和

$\sum_i^n \sigma (i)=\sum_i^ni\left \lfloor \frac{n}{i} \right \rfloor$

公约数约数和

$\sum_i^n \sigma (gcd(i,j)) \\~~=\sum_i^n\sum_{d|i,n}d \\~~=\sum_{d|n}d\frac{n}{d} \\~~=nd(n)$

1..n中与n互质的数的和

$g(n)=\sum_i^nie(gcd(i,n)) \\~~~~~~~~~~~=\sum_i^ni\sum_{d|i,n}\mu(d) \\~~~~~~~~~~~=\sum_{d|n}\mu(d)\sum_{d|i,i\leqslant n}i \\~~~~~~~~~~~=\sum_{d|n}\mu(d)\frac{n(\frac{n}{d}+1)}{2} \\~~~~~~~~~~~=\frac{n}{2}(\mu \times id+\mu \times 1) \\~~~~~~~~~~~=\frac{n}{2}(\varphi + e)$

1D lcm sum

$\sum_i^n lcm(i,n) \\~~=n\sum_i^n\frac{i}{gcd(i,n)} \\~~=n\sum_{d|n}\frac{\sum_{i\leqslant n}i[gcd(i,n)=d]}{d} \\~~=n\sum_{d|n}\sum_j^{\frac{n}{d}}je(gcd(j,\frac{n}{d})) \\~~=n\sum_{d|n}g(\frac{n}{d}) \\~~=n(g \times 1)$

1..n与1..m所有数对的乘积和

$Sum(n,m)=\sum_i^n\sum_j^mij \\~~=\frac{n(n+1)m(m+1))}{4}$

1..n与1..m中互质的数对的乘积和

$S(n,m)=\sum_i^n\sum_j^mije(gcd(i,j)) \\~~~~~~~~~~~~~~~~=\sum_i^n\sum_j^mij\sum_{d|i,j}\mu(d) \\~~~~~~~~~~~~~~~~=\sum_{d\leqslant n}\mu(d)Sum(\left \lfloor \frac{n}{d} \right \rfloor ,\left \lfloor \frac{m}{d} \right \rfloor)$

2D lcm sum level 1

$~lcm \ sum \ level \ 1 \\~~~~~~\sum_i^n\sum_j^m lcm(i,j) \\~~=\sum_i^n \sum_j^m \frac{ij}{gcd(i,j)} \\~~=\sum_i^n \sum_j^m \sum_{d|i,j}\frac{ij[gcd(i,j)=d]}{d} \\~~=\sum_{d\leqslant n}dS(\left \lfloor \frac{n}{d} \right \rfloor,\left \lfloor \frac{m}{d} \right \rfloor)$

我们定义一个函数

$f(n)=\frac{1}{n}$

它不是整数……但很有用

顺手定义

$F=f \times \mu$

即

$f=F \times 1$

2D lcm sum level 2

$~lcm \ sum \ level \ 2 \\~~~~~~\sum_i^n\sum_j^m lcm(i,j) \\~~=\sum_i^n \sum_j^m ijf(gcd(i,j)) \\~~=\sum_i^n \sum_j^m ij\sum_{d|i,j}F(d) \\~~=\sum_{d\leqslant n}d^2F(d)Sum(\left \lfloor \frac{n}{d} \right \rfloor,\left \lfloor \frac{m}{d} \right \rfloor) \\~~=\sum_{d \leqslant n}d^2 \sum_{d'|d} f(d') \mu(\frac{n}{d'})Sum(\left \lfloor \frac{n}{d} \right \rfloor,\left \lfloor \frac{m}{d} \right \rfloor) \\~~=\sum_{d \leqslant n}d \sum_{d'|d} d f(d') \mu(\frac{d}{d'})Sum(\left \lfloor \frac{n}{d} \right \rfloor,\left \lfloor \frac{m}{d} \right \rfloor) \\~~=\sum_{d \leqslant n}d \sum_{d'|d} \frac{d}{d'} \mu(\frac{d}{d'})Sum(\left \lfloor \frac{n}{d} \right \rfloor,\left \lfloor \frac{m}{d} \right \rfloor) \\~~=\sum_{d \leqslant n}id (id\mu \times 1)Sum(\left \lfloor \frac{n}{d} \right \rfloor,\left \lfloor \frac{m}{d} \right \rfloor)$

上面这个式子最后一行的Sum前面应该加上"(d)"= = 、

积性函数筛出来,分块统计

怎样分块统计?

n/d,m/d最多有sqrt(n)+sqrt(m)中取值

f是非分块统计部分的[i,j]的区间和

Sum代表的是一系列可以分块统计的函数

for(int i=1,j;i<=n;i=j+1){
	j=min(n/(n/i),m/(m/i));
	ans+=(f[j]-f[i-1])*(Sum(n/i,m/i));
}

怎样线性筛积性函数?

for(int i=2;i<maxn;i++){
	if(!p[i]){
		prime[++prime[0]]=i;
		//A
	}for(int j=1;j<=prime[0]&&i*prime[j]<maxn;j++){
		p[i*prime[j]]=1;
		if(i%prime[j]==0){
			//B
			break;
		}else{
			//C
		}
	}
}

欧拉筛把积性函数 $f(n)$ 分成了三类

A:n为质数

B:n最小质因子为p且次数大于1

C:n最小质因子为p且次数为1
现在我们要计算一个积性函数 $f(n)$

A:质数通常很简单,特判

C:显然i与p互质那么 $f(ip)=f(i)f(p)$
B类比较复杂

但显然

$f(n)=f(p^k)f(\frac{n}{p^k})$

所以我们记录n的最小质因子的幂

问题转化为如何求 $f(p^k)$

这就与函数本身相关了

比如

$\varphi (p^k)=p^k-p^{k-1} \\ ~~~~~\mu(p^k)=0$

对于2D lcm sum level 2

$id\mu \times 1 (p^k)=id\mu \times 1 (p)$

宇宙最快求和法

求

$S(n)=\sum_{i=1}^n f(i)$

设

$g(n)=\sum_{d|n}f(d)$

那么

$S(n)=\sum_{i=1}^nf(i) \\~~~~~~~~~~~=\sum_{i=1}^n(g(i)-\sum_{d|i,d\neq i}f(d)) \\~~~~~~~~~~~=\sum_{i=1}^ng(i) - \sum_{i=2}^nS(\left \lfloor \frac{n}{i} \right \rfloor)$