狄利克雷卷积&莫比乌斯反演总结

Prepare

1、([P])表示当(P)为真时([P])为(1)，否则为(0)。

2、(a|b)指(b)被(a)整除。

3、一些奇怪常见的函数:

(1(n)=1)

(id(n)=n)

(sigma(n)=n的约数和)

(d(n)=n的约数个数)

(epsilon(n)=[n==1])

狄利克雷卷积

数论函数

数论函数指一类定义域是正整数，值域是一个数集的函数。

加法：逐项相加就可以辣((f+g)(x)=f(x)+g(x))

数乘：用一个常数乘((xf)(n)=x*f(n))

狄利克雷卷积

定义两个数论函数的狄利克雷卷积(*)：

若(t=f*g)则

[t(n)=sum_{i|n}f(i)g(frac{n}{i}) ]

等价于

[t(n)=sum_{ij=n}f(i)g(j) ]

狄利克雷卷积有以下性质(两个数论函数相等，是指两个函数的每一项都相等)：

1、交换律(f*g=g*f)

2、结合律(f*(g*h)=(f*g)*h)

3、分配律(f*h+g*h=(f+g)*h)

4、没有名字((xf)*g=x(f*g))

5、单位元(epsilon*f=f)，其中(epsilon(n)=[n==1])

6、逆元:对于每一个(f(1) eq 0)的函数(f)，都有(f*g=epsilon)

讨论一下第六个结论，如何求一个函数的逆呢？

只需要定义

[g(n)=frac{1}{f(1)}left([n==1]-sum_{i|n,i eq 1}f(i)g(frac{n}{i}) ight) ]

这样的话

[sum_{i|n}f(i)g(frac{n}{i})=f(1)g(n)+sum_{i|n,i eq1}f(i)g(frac{n}{i})=[n==1] ]

积性函数

如果一个数论函数(f)有当(gcd(n,m)==1)时

[f(nm)=f(n)f(m) ]

就称(f)为积性函数。

一些常见的积性函数：

(epsilon(n)=[n==1]),(id(n)=n),(id^{k}(n)=n^k)

事实上他们也满足完全积性(即当(gcd(n,m) eq1)时，也有(f(nm)=f(n)f(m)))

特殊的，我们令(id^0(n)=1(n)=1)

还有两个普通的积性函数

(d(n)=n的约数和)、(varphi(n)=[1,n]中与n互质的数的个数)

还有两个重要结论：

两个积性函数的狄利克雷卷积是积性函数。

积性函数的逆是积性函数。

积性函数有什么用呢？

它可以线性筛

然而还有更有用的(---)

莫比乌斯反演

一些理论

我们定义(1)的逆是(mu)

这样的话，如果(g=f*1)，就有(f=f*1*mu=g*mu)

换句话说，就是

[g(n)=sum_{d|n}f(d)Leftrightarrow f(n)=sum_{d|n}mu(frac{n}{d})g(d) ]

也可以这样子

[g(d)=sum_{d|n}f(n)Leftrightarrow f(d)=sum_{d|n}mu(frac{n}{d})*g(n) ]

例子

怎么用呢？举几个例子(以下情况默认(nleq m))

(Eg1)

求

[sum_{i=1}^nsum_{i=1}^m[gcd(i,j)==1] ]

然后怎么办呢？

设

[f(x)=sum_{i=1}^nsum_{i=1}^m[gcd(i,j)==x] \ g(x)=sum_{x|d}f(d) ]

则

[f(1)=sum_{1|d}mu(frac{d}{1})g(d) \ f(1)=sum_{i=1}^nmu(i)g(i) ]

考虑(g(x))是什么

[g(x)=sum_{x|d}sum_{i=1}^nsum_{i=1}^m[gcd(i,j)==d] ]

即

[g(x)=sum_{i=1}^nsum_{i=1}^m[x|gcd(i,j)] \ g(x)=sum_{i=1}^{leftlfloorfrac nx ight floor}sum_{i=1}^{leftlfloorfrac mx ight floor}[1|gcd(i,j)]\ g(x)=leftlfloorfrac nx ight floorleftlfloorfrac mx ight floor ]

带回(f(1))

[Ans=sum_{x=1}^nmu(x)leftlfloorfrac nx ight floorleftlfloorfrac mx ight floor ]

这个用整除分块可以做到(O(sqrt n))

(Eg2)

求

[sum_{i=1}^nsum_{j=1}^mgcd(i,j) ]

可化为

[sum_{d=1}^nsum_{i=1}^nsum_{j=1}^md[gcd(i,j)==d] \ sum_{d=1}^ndsum_{i=1}^{leftlfloorfrac nd ight floor}sum_{j=1}^{leftlfloorfrac md ight floor}[gcd(i,j)==1] ]

设

[x=leftlfloorfrac nd ight floor, y=leftlfloorfrac md ight floor ]

则

[sum_{d=1}^ndsum_{i=1}^xsum_{j=1}^y[gcd(i,j)==1] ]

套入我们刚才在(Eg1)求得的

[sum_{d=1}^ndsum_{i=1}^xmu(i)leftlfloorfrac xi ight floorleftlfloorfrac yi ight floor\ sum_{d=1}^ndsum_{i=1}^{n/d}mu(i)leftlfloorfrac {x}{id} ight floorleftlfloorfrac {y}{id} ight floor ]

化到现在是(O(n))的，因为前后都可以数论分块

但是我们能做得更好

令(T=id)

原式化为

[sum_{d=1}^ndsum_{i=1}^nmu(i)leftlfloorfrac {x}{T} ight floorleftlfloorfrac {y}{T} ight floor\ sum_{T=1}^nleftlfloorfrac {x}{T} ight floorleftlfloorfrac {y}{T} ight floorsum_{d|T}dmu(frac Td) ]

乍一看还是(O(n))的呀，但是对于后面那一坨

[f(T)=sum_{d|T}dmu(frac Td)\ Leftrightarrow\ f(T)=sum_{ij=T}id(i)mu(j) ]

两个积性函数相乘，可以线性筛呀！！

所以复杂度被我们压到了(O(sqrt n))

(upd;on;2019.3.9:)

发现以前没有讲线性筛，导致现在自己都不知道是怎么搞得了。。。

线性筛

我们筛(mu)的函数是长这样的(自动认为有模数)：

int prime[MAX_N], mu[MAX_N]
bool nprime[MAX_N]; 
void sieve() { 
	mu[1] = 1;
	for (int i = 2; i <= N; i++) {
		if (!nprime[i]) prime[++tot] = i, mu[i] = Mod - 1; 
		for (int j = 1; i * prime[j] <= N; j++) { 
			nprime[i * prime[j]] = 1; 
			if (i % prime[j] == 0) break; 
			mu[i * prime[j]] = Mod - mu[i]; 
		} 
	} 
}

其实就是和筛素数的是一样的，

if (i % prime[j] == 0) break;

这句话保证了复杂度，因为你存的素数是递增的，

如果(i)被(prime[j])整除后，(i*prime[j+k](k>0))一定可以被(prime[j]*x)的形式表示出来。

那么就有我们下面的一个问题：

(Eg3)

给定你一个数组(f)，求

[sum_{i=1}^nsum_{j=1}^mf[gcd(i,j)] ]

其中(n,mleq 10^7)，数据组数(Tleq 10^4)。

由我们上面推的东西，将(f)看作一个数论函数，可以知道只要求出一个函数(g=mu * f)的前缀和，

这个问题就解决了。

一下是解决这个问题的几种方法(蒯的)：

void get_g_1(int N, const int *f, int *g) {
  for (int i = 1; i <= N; i++) g[i] = 0;
  for (int i = 1; i <= N; i++)
    for (int j = 1; i * j <= N; j++)
      g[i * j] = (g[i * j] + mu[i] * f[j]) % mod;
} // 依照定义，O(nlogn)

void get_g_2(int N, const int *f, int *g) {
  for (int i = 1; i <= N; i++) g[i] = f[i];
  for (int i = 1; i <= N; i++)
    for (int j = 2; i * j <= N; j++)
      g[i * j] = (g[i * j] - g[i]) % mod;
} // 类似求狄利克雷卷积逆的方式，不需要线性筛 mu ，O(nlogn)

void get_g_3(int N, const int *f, int *g) {
  for (int i = 1; i <= N; i++) g[i] = f[i];
  for (int i = 0; i < prime_count; i++)
    for (int j = N / prime[i]; j >= 1; j--)
      g[j * prime[i]] = (g[j * prime[i]] - g[j]) % mod;
} // Magic! O(nloglogn)

对于最后一种方法，理解成dp：

[g_{i,n}=sum_{d|n,d只包含前i种质因子}mu(d)f(n/d) ]

那么转移：

[g_{i,n}=egin{cases} g_{i-1,n};;;;;;;;;;;;;;;;;;;;p_i mid n\ g_{i-1,n}-g_{i-1,n/p_i};;;;;p_imid n end{cases} ]

复杂度(O(nloglog n))。

参考文章1

参考文章2