莫比乌斯反演

· · 个人记录

joke3579大佬一直劝说我来切莫反

于是我切了一顿发现我一道都不会

所以写个这么个东西来稍微总结一下

莫比乌斯反演

首先莫比乌斯函数和狄利克雷卷积我就不说是什么东西了

整除分块不会的去看oiwiki抄一份过来就行

直接进入正题

反演公式

若f(n)=\sum\limits_{d|n}g(d),则有g(n)=\sum\limits_{d|n}\mu(d)f(\frac{n}{d})

证明自己看课件 不解释 实际上感觉在搞这几道题的时候基本没有在用这个 都是在套路

然后说几个小东西 一律不证明

1.\sum\limits_{d|n}\mu(d)=[n=1]

2.\sum\limits_{d|n}\phi(d)=n (有时候会用到)

然后开始吧 首先来一些简单的板子吧

注：以下均假定n<=m

1.P3455

题面：求

\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=d]

首先我们入门先讨论d=1的情况

当d=1时，我们可以采用我们刚才的小东西来搞他一下

\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1] =\sum_{i=1}^n\sum_{j=1}^m\sum_{d|\gcd(i,j)}\mu(d) =\sum_{i=1}^n\sum_{j=1}^m\sum_{d|i,d|j}\mu(d)

然后是一个常见的套路，把我们要的d提到前面来 在很多这种情况都适用的

=\sum_{d=1}^{n}\mu(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor

解释一下后面那两个东西：

首先我们把d提前了，我们就要算每个i，j对d的贡献度。

因为d|i,d|j,所以对于任意i,都有i=kd,k是一个常数。j同理。

然后放下j不管，只看i，每个d总共会被统计\lfloor\frac{n}{d}\rfloor次。

j按照同样的方式计算，于是就出了这个看起来比较正常的柿子。

而我们知道这个东西可以整除分块O(\sqrt n)搞出来

所以线性筛出\mu的前缀和就可以乱搞了

然后是这个题，d是任意数的情况。根据gcd的性质，我们直接把所有东西除一个d，变成如下形式：

\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i,j)=1]

然后就变成上面的板子了。

双倍经验：P2522 Problem B

就是i从a开始，j从b开始，容斥成四个上面的东西搞就行了。

2.一些不一样的东西

P2257 YY的GCD

题意：求

\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)\in prime]

某种程度上这个题和题库的后面所有题都是差不多类的 提供了一种新的优化方法

接下来先按照我们刚才看到的东西来化一下

\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)\in prime] =\sum_{k\in prime}\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k] =\sum_{k\in prime}\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[\gcd(i,j)=1] =\sum_{k\in prime}\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}\sum_{d|\gcd(i,j)}\mu(d) =\sum_{k\in prime}\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)\lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor

于是我们把所有的质数筛出来然后大力分块搞就行了……吗？

（我没敢交）

反正无论如何我们还得优化就是了

这里还有一个常用的东西：我们设T=kd，则原式

=\sum_{k\in prime}\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor

把T提前，于是有：

=\sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)(k\in prime)

然后因为T=kd,所以d=\frac{T}{k},于是原式

=\sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{d|T}\mu(\frac{T}{d})(d\in prime)

把第二个\sum后面的东西提出来，我们如果有它的前缀和就可以O(\sqrt n)搞了。发现这个东西可以和素数一起筛出来。你问我怎么筛？

分析后面这一坨东西的性质，既然只在d是质数的时候有贡献那么直接预处理一顿就行了。具体实现如下：

void getmiu() {
    mu[1]=1;
    for (int i=2;i<=10000000;i++) {
        if (!notprime[i]) prime[++cnt]=i,mu[i]=-1;
        for (int j=1;j<=cnt&&i*prime[j]<=10000000;j++) {
            notprime[i*prime[j]]=1;
            if (i%prime[j]==0) break;
            mu[i*prime[j]]=-mu[i];
        }
    }
    for (int i=1;i<=cnt;i++)
        for (int j=1;prime[i]*j<=10000000;j++)
            f[j*prime[i]]+=mu[j];//这一行直接把所有能造成贡献的数累加
    for (int i=1;i<=10000000;i++)
        sum[i]=sum[i-1]+f[i];
}

结束。

当然，也有一些题的函数可以线性筛出来。比如下题：

P4449 于神之怒加强版

题意：

\sum_{i=1}^n \sum_{j=1}^m \gcd(i,j)^k

（jzptab那个题其实差不多但是我不想写lcm因为latex木有\lcm这东西）

看到gcd第一反应开始代换：

=\sum_{e=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{m}e^k(\gcd(i,j)=e) =\sum_{e=1}^n\sum_{i=1}^{\lfloor\frac{n}{e}\rfloor}\sum_{j=1}^{\lfloor\frac m e \rfloor}e^k\sum_{d|\gcd(i,j)}\mu(d) =\sum_{e=1}^{n}e^k\sum_{d=1}^{\lfloor\frac n e \rfloor}\mu(d)\lfloor \frac n{ed} \rfloor\lfloor\frac m{ed}\rfloor

然后按照套路，设T=ed

=\sum_{e=1}e^k\sum_{d=1}^{\lfloor\frac ne\rfloor}\mu(d)\lfloor\frac nT\rfloor\lfloor\frac mT\rfloor =\sum_{T=1}^{n}\lfloor\frac nT\rfloor\lfloor\frac mT\rfloor\sum_{d|T}d^k\mu(\frac Td)

首先后面这一堆东西显然是我们熟悉的狄利克雷卷积形式，而\mu和I_k都是积性函数，所以这后面一堆也是积性的，可以线性筛。就先设：

f(T)=\sum\limits_{d|T}d^k\mu(\lfloor\frac Td\rfloor)

接下来问题来了：怎么筛？

首先我们线性筛大概分两部分：

第一部分，判断i是不是素数。

第二部分，筛掉i的倍数。

于是我们从这两部分下手。首先线性筛从2开始，所以特判1。手模一下，显然f(1)=1。

然后是第一部分。如果T是素数的话，那么T的因数只有1和他本身。手模一下，有

f(p)=\mu(p)+p^k=p^k-1

然后讨论第二部分。首先既然f(T)是个积性函数，那么只要i不是prime[j]的倍数就直接嗯乘就可以了。即：

f[i*prime[j]=f[i]*f[prime[j]];

然后是prime[j]|i的情况。因为i*prime[j]刚好比i多一个质因子prime[j],所以根据积性函数性质，有

f(p^{x_i})=f(p^{x_i-1})*p

于是直接搞就行了，别忘了处理前缀和。把线性筛代码放下面了。

void getmiu(){
    f[1]=1;
    for(int i=2;i<=5000000;i++){
        if(!v[i]){
            p[++p[0]]=i;
            g[p[0]]=qpow(i,k);
            f[i]=(g[p[0]]-1+mod)%mod;
        }
        for(int j=1;j<=p[0]&&i*p[j]<=5000000;j++){
            v[i*p[j]]=true;
            if(i%p[j]==0){
                f[i*p[j]]=1ll*f[i]*g[j]%mod;break;
            }
            f[i*p[j]]=1ll*f[i]*f[p[j]]%mod;
        }
    }
    for(int i=1;i<=5000000;i++)f[i]=(f[i-1]+f[i])%mod;
}

jzptab那个题和这个差不多，就是最后的函数不积性，但是也能线性筛。

DZY Loves Math那个线性筛稍微难一点，但是joke3579大佬埃式筛卡常过去了。

接下来是第三类：

3.P3704 数字表格

（不要被黑题吓到，这原先是紫题）

题意：求

\prod_{i=1}^n\prod_{j=1}^mf(\gcd(i,j))

其中f(x)为Fibonacci第x项。

斐波那契数列似乎没什么性质。没关系，先放着他，用里面的gcd来搞。

=\prod_{k=1}^n\prod_{i=1}^n\prod_{j=1}^mf(k)(\gcd(i,j)=k)

按照套路，我们该把第二个和第三个\prod上的n变成\lfloor\frac nk \rfloor了，但是这是乘法，怎么办？

参考当时\sum的做法，当时我们由于少加了，直接在后面乘一个k^2。这里同理，多乘几次不就得了。多乘几次是什么？乘方！

=\prod_{k=1}^nf(k)^{\sum_{i=1}^{\lfloor\frac nk\rfloor}\sum_{j=1}^{\lfloor\frac mk\rfloor}(\gcd(i,j)=1)}

然后我们把上面一堆东西整出来：

\sum_{i=1}^{\lfloor\frac nk\rfloor}\sum_{j=1}^{\lfloor\frac mk\rfloor}\gcd(i,j)=1

不就是我们之前搞过的东西吗！

=\sum_{d=1}^{\lfloor\frac nk\rfloor}\mu(d)\lfloor\frac n{kd}\rfloor\lfloor\frac m{kd}\rfloor

这个东西已经好很多了，卡常卡的好应该可以暴艹过去。但是如果你不是卡常大师应该会怒t所以继续套路：

设T=kd，于是把这个东西再从指数上扔下来。我们之前把乘法换成\sum扔下来，现在指数也相应得搞成\prod：

=\prod_{k=1}^nf(k)^{\sum_{d=1}^{\lfloor\frac nk\rfloor}\mu(d)\lfloor\frac nT\rfloor\lfloor\frac mT\rfloor} =\prod_{T=1}^n\prod_{d|T}f(d)^{\mu(\lfloor\frac Td\rfloor)\lfloor\frac nT\rfloor\lfloor\frac mT\rfloor}

然后发现这一堆东西可以整个函数：

g(T)=\prod_{d|T}f(d)^{\mu(\lfloor\frac Td\rfloor)}

但是指数上的东西似乎没法正常筛。那怎么办？

观察数据范围，1e6，似乎没有卡那么死。于是：

暴力枚举！

for(int i=1;i<=1000000;i++){
        for(int j=1;i*j<=1000000;j++){
            g[i*j]=1ll*g[i*j]*mypow(i,miu[j])%mod;
        }
    }

最后关于约数个数和这个题，给个柿子自己搞去：

d(ij)=\sum_{x|i}\sum_{y|j}[\gcd(i,j)=1]

祝学的愉快！（虽然我巧了这两百多行的latex并不是很愉快）