莫比乌斯反演

狄利克雷卷积

$$h(n)=(f\ast g)(n)=\sum _ { i|n }f(i)\cdot g(\frac{n}{i})=\sum _ { ab=x }f(a)\cdot g(b)\\ 记为h=f\ast g\\ 交换律f\ast g=g\ast f，显然由上式，交换仅仅是ab交换，相等\\ 结合律(f\ast g)\ast h=f\ast (g\ast h)\\ 分配律f\ast(g+h)=f\ast g+f\ast h\\ 单位元f\ast \varepsilon=f\\ 若f和g都是积性函数，则f\ast g为积性函数\\ f=g的充要条件是f\ast h=g\ast h，其中保证h(1)\ne 0\\ 若f\ast g=\varepsilon，则f和g互为逆元\\ 积性函数必然有逆元，逆元也是积性函数\\ $$

常见卷积公式

$$\varepsilon=\mu\ast 1\\d=1\ast 1\\\sigma=id\ast 1\\\varphi\ast 1=id\\ $$

积性函数线性筛

利用欧拉筛的方法，显然容易线性筛出任何积性函数

void getf()
{
    f[1]=;
    rep(i,2,n)
    {
        if (!notprime[i]) prime[++tot]=i,f[i]=(式子1);
        for (int j=1;j<=tot&&i*prime[j]<=n;j++)
        {
            notprime[i*p[j]]=1;
            if (i%prime[j]==0)
            {
                f[i*prime[j]]=(式子2);
                break;
            }
            f[i*prime[j]]=(式子3);
        }
    }
}

式子1 质数，式子2 质数prime[j]的指数增加了一，式子3 互质

比如筛莫比乌斯函数时，式子1为-1，式子2为0，式子3为-f[i]

筛欧拉函数时，式子1为i-1,式子2为f[i]*prime[j],式子3为phi[i]*(prime[j]-1)

数论分块

含有$\lfloor\frac{n}{i}\rfloor$的求和式，如$\sum _ {i=1} ^ {n} \lfloor\frac{n}{i}\rfloor\cdot f(i)$，容易发现$\lfloor\frac{n}{i}\rfloor$的取值只有$\sqrt n$种。设当前值的左界为l，有界为r，则一个方便的跳l、r的方式是l=r+1,r=n/(n/l)。如果$f(x)$能用求和公式表示，那么整个式子的值就能在$O(\sqrt{n})$的时间复杂度内完成

做了一道模板题Luogu P2261，因为太显然了，就不单独发blog，这里也不贴代码了。

二维数论分块

$$\sum _ {i=1} ^ {min(n,m)} \lfloor \frac{n}{i}\rfloor \cdot \lfloor \frac{m}{i}\rfloor$$

只是把跳$\sqrt{n}$次变成$2\sqrt{n}$次罢了，找n和m的跳跃点中最近的位置跳即可。

莫比乌斯反演

$$f(n)=\sum _ {d|n} g(d)\Longleftrightarrow g(n)=\sum _ {d|n} \mu(d)f(\frac{n}{d})\\ f=g\ast 1\Longleftrightarrow g=f\ast \mu$$

由前文狄利克雷卷积部分知识，显然。

如何应用

场景一

$$g(i)难求，但f(i)=\sum _ {d|i} g(d) 较容易求，则利用下式：\\ f(i)=\sum _ {d|i} g(d)\Rightarrow g(i)=\sum _ {d|i} f(\frac{i}{d})\cdot\mu(d)$$

场景二

$$g(i)难求，但f(i)=\sum _ {d=1} ^ {\lfloor\frac{n}{i}\rfloor}g(d\cdot i)容易求，则利用下式\\ f(i)=\sum _ {d=1} ^ {\lfloor\frac{n}{i}\rfloor} g(d\cdot i)\Rightarrow g(i)=\sum _ {d=1} ^ {\lfloor\frac{n}{i}\rfloor} f(d\cdot i) \cdot\mu (d)$$

技巧

等价变换：改变枚举顺序（内层外移）、变量替换等技巧

线性筛：线性处理各种信息

数论分块：重要工具

例1：

经过转化之后，问题的核心是
$$\sum _ {i=1} ^ {\lfloor\frac{n}{k}\rfloor} \sum _ {j=1} ^ {\lfloor\frac{m}{k}\rfloor} (gcd(i,j)==1)$$

解：

看到==1这种东西，首先想到单位元函数
$$原式=\sum _ {i=1} ^ {\lfloor\frac{n}{k}\rfloor} \sum _ {j=1} ^ {\lfloor\frac{m}{k}\rfloor} \varepsilon(gcd(i,j))\\ =\sum _ {i=1} ^ {\lfloor\frac{n}{k}\rfloor} \sum _ {j=1} ^ {\lfloor\frac{m}{k}\rfloor}\sum _ {d|gcd(i,j)} \mu(d)\ \ 莫比乌斯反演\\ =\sum _ {d=1} ^ {min{\lfloor\frac{n}{k}\rfloor,\lfloor\frac{m}{k}\rfloor}}\mu(d)\lfloor\frac{m}{k\cdot d}\rfloor\lfloor\frac{n}{k\cdot d}\rfloor$$
其中推导的最后一步更换了枚举的变量。可以发现，倒数第二个式子中，对于每个$d$，当$d|i或 d|j$时$\mu(d)$都会被加一次，因此可以得到最终的式子。

而最终的式子显然可以在预处理出莫比乌斯函数的前缀和后通过上面提到的二维数论分块的思路来快速解决

例2

求
$$\sum _ {i=1} ^ n \sum _ {j=1} ^ m \gcd(i,j)$$

解：

利用常见卷积的公式，
$$原式=\sum _ {i=1} ^ n \sum _ {j=1} ^ m \sum _ {d|\gcd(i,j)} \varphi(d)\\ =\sum _ {d=1} \varphi(d) \cdot \lfloor\frac{n}{d} \rfloor \cdot \lfloor\frac{m}{d}\rfloor$$
接下来处理和例1相同

例3 SPOJ5971 LCMSUM

$$\sum _ {i=1} ^ {n} lcm(i,n)$$

3e5组询问，n范围1e6

解：

$$原式=\sum _ {i=1} ^ {n} \frac{i\cdot n}{\gcd(i,n)}\\ =\sum _ {d|n} \sum _ {i=1} ^ {n} \frac{i\cdot n}{d}[\gcd(i,n)==d]\\ =n\cdot\sum _ {d|n} \sum _ {i=1} ^ {\lfloor \frac{n}{d}\rfloor} \frac{i}{d}[\gcd(i,\frac{n}{d})==1],改变枚举的变量i的意义\\ =n\cdot \sum _ {d|n} \sum _ {i=1} ^ {d} i\cdot [\gcd(i,d)==1],由于枚举d和枚举\frac{n}{d}等价\\ =n\cdot \sum _ {d|n} \frac{d\cdot \varphi(d)+[d==1]}{2},上文\varphi函数的性质一节中提到的公式\\ =\frac{n}{2}\cdot (\sum _ {d|n} \varphi(d)\cdot d+1),推导显然$$

至此可以得到$O(n)$预处理出欧拉函数，$O(\sqrt{n})$回答询问的方法。但是这样会TLE

考虑将答案函数预处理：显然可以在调和级数复杂度下做出来。总复杂度$O(n\lg n+T)$

通过推导可以发现，$\sum _ {d|n}\varphi(d)\cdot d$是个积性函数，可以线性预处理，因此可以做到$O(n+T)$，具体证明待补

例4

$$\sum _ {i=1} ^ {n} \sum _ {j=1} ^ m lcm(i,j)$$

解：

$$原式=\sum _ {i=1} ^ {n} \sum _ {j=1} ^ m \frac{i\cdot j}{\gcd(i,j)}\\ =\sum _ {i=1} ^ {n} \sum _ {j=1} ^ m \frac{i\cdot j}{d}[gcd(i,j)==d]\\ =\sum _ {d=1} ^ n \sum _ {i=1} ^ {\lfloor\frac{n}{d}\rfloor} \sum _{j=1} ^ {\lfloor\frac{m}{d}\rfloor} i\cdot j\cdot d[gcd(i,j)==1]\\ =\sum _ {d=1} ^ {n} d\cdot\sum _ {i=1} ^ {\lfloor \frac{n}{d}\rfloor}i \sum _ {j=1} ^ {\lfloor \frac{m}{d}\rfloor} j\sum _ {k|\gcd(i,j)}\mu(k)\\ =\sum _ {k=1} ^ {n} k^2\mu(k)\sum _ {d=1} ^ {n} d\sum _ {i=1}^{\lfloor \frac{n}{dk}\rfloor}i \sum _ {j=1}^ {\lfloor \frac{m}{dk}\rfloor} j\\ 下面设f(x)=\sum _ {i=1} ^ {x} i,设T=nk\\ =\sum _ {T=1} ^ n \sum _ {d|T} \frac{T^2}{d^2} d\mu(\frac{T}{d})f(\frac{n}{T})f(\frac{m}{T})\\ =\sum _ {T=1} ^ n f(\frac{n}{T}) f(\frac{m}{T}) \cdot T\sum _ {d|T} d\cdot\mu(d)\\ 其中F(x)=\sum _ {d|T} d\cdot\mu(d)可以证明是一个积性函数，可以O(n)筛出来，前面部分数论分块即可$$

例5 SDOI2015 约数个数和

$$\sum _ {i=1} ^ {n} \sum _ {j=1} ^ m d(i\cdot j)$$

解：

$$首先利用约数个数函数的重要性质d(i\cdot j)=\sum _ {d|i} \sum _ {d|j} [\gcd(i,j)==1]\\ 则原式=\sum _ {i=1} ^ {n} \sum _ {j=1} ^ {m} \sum _ {d|i} \sum _ {d|j} [\gcd(i,j)==1]\\ =\sum _ {i=1} ^ {n} \sum _ {j=1} ^ m \sum _ {d=1} ^ {i} \mu(d)\cdot \lfloor \frac{i}{d}\rfloor \cdot \lfloor \frac{j}{d} \rfloor\\ =\sum _ {d=1} ^ n \mu(d) \cdot \sum _ {i=1} ^ n \lfloor \frac{i}{d}\rfloor \cdot \sum _ {j=1} ^ m \lfloor \frac{j}{d} \rfloor\\ 数论分块即可$$

例6 SDOI2017 数字表格

$$\prod _ {i=1} ^ {n} \prod _ {j=1} ^ m fib(\gcd(i,j))\\ n,m\le 10^6,T\le1000,fib(0)=0$$

解：

只1是把问题放到了指数上罢了。斐波那契数列显然和数论要用的这些没什么大关系，所以先常规操作：
$$原式=\prod _ {i=1} ^ n \prod _ {j=1} ^ m f(d) ^ {[\gcd(i,j)=d]}\\ =\prod _ {d=1} \prod _ {i=1} ^ {\lfloor \frac{n}{d}\rfloor}\prod _ {j=1} ^ {\lfloor \frac{m}{d}\rfloor} f(d)^{[\gcd(i,j)=1]}\\ =\prod _ {d=1} \prod _ {i=1} ^ {\lfloor \frac{n}{d}\rfloor}\prod _ {j=1} ^ {\lfloor \frac{m}{d}\rfloor} \prod _ {k|\gcd(i,j)} f(d)^{\mu(k)}\\ =\prod _ {d=1}\prod _ {k=1} \prod _ {i=1} ^ {\lfloor \frac{n}{dk}\rfloor}\prod _ {j=1} ^ {\lfloor \frac{m}{dk}\rfloor} f(d)^{\mu(k)}\\ =\prod _ {T=1} ^ n \prod _ {d|T} f(d) ^ {\lfloor\frac{n}{T}\rfloor\cdot \lfloor\frac{m}{T}\rfloor\cdot\mu(\frac{T}{d})}\\ 乍一看似乎没法继续推下去了，考虑把不能数论分块的部分提出\\ =\prod _ {T=1} ^ n (\prod _ {d|T} f(d)^{\mu(\frac{T}{d})})^{\lfloor\frac{n}{T}\rfloor\cdot\lfloor\frac{m}{T}\rfloor}\\ 其中括号内的部分可以求前缀积，指数数论分块即可$$

例7 BZOJ4407 于神之怒加强版

$$\sum _ {i=1} ^ n \sum _ {j=1} ^ m \gcd(i,j)^k\\ n,m\le5\cdot 10^6,T\le 2000$$

解：

$$原式=\sum _ {d=1} ^ n \sum _ {i=1} ^ {\lfloor \frac{n}{d}\rfloor} \sum _ {j=1} ^ {\lfloor \frac{m}{d} \rfloor} d^k\cdot[gcd(i,j)=1]\\ =\sum _ {T=1} ^ n \lfloor\frac{m}{T}\rfloor\lfloor\frac{n}{T}\rfloor\sum _ {d|T} d^k\mu(\frac{T}{d}),常规操作\\ 可以发现右边的式子是\sigma_k\ast \mu，显然是积性函数，可以线性预处理出来。询问时数论分块$$

例8 BZOJ2820 YY的GCD

$$\sum _ {i=1} ^ {n} \sum _ {j=1} ^ {m} [\gcd(i,j)\in prime]\\ n,m\le10^7$$

解：

$$先常规操作，得\\ 原式=\sum _ {T=1} ^ {n} \lfloor\frac{n}{T}\rfloor \cdot \lfloor \frac{m}{T}\rfloor \sum _ {k|T,k\in prime} \mu(\frac{T}{k})\\ 右式可以预处理，由于处理次数是\sum _ {p=1} ^ n {\lfloor\frac{n}{p}\rfloor}[p\in prime] ,因此复杂度小于调和级数\\ 考虑质数个数粗略估计是\frac{n}{\lg n},调和级数求和复杂度O(n\lg n)，因此复杂度应该是接近O(n)的$$

例9 HDU4944 FSF’s game

$$\sum _ {i=1} ^ n \sum _ {j=i} ^ n \sum _ {d|i,j} \frac{ij}{\gcd(\frac{i}{d},\frac{j}{d})}\\ T=500000,n\le500000$$

解：

首先看到这个gcd在分母上这个样子，很难受，同时形式很像是lcm，考虑转化
$$原式=\sum _ {i=1} ^ n \sum _ {j=i} ^ {n} \sum _ {d|\gcd(i,j)} d\cdot lcm(i,j)\\ =\sum _ {d=1} ^ n d^2\sum _ {i=1} ^ {\lfloor\frac{n}{d}\rfloor} \sum _ {j=i} ^ {\lfloor\frac{n}{d}\rfloor}lcm(i,j)\\ 调换ij位置=\sum _ {d=1} ^ n d^2\sum _ {i=1} ^ {\lfloor\frac{n}{d}\rfloor}\sum _ {j=1} ^ {i} lcm(i,j)\\ 由例3，=\sum _ {d=1} ^ n d^2\sum _ {i=1} ^ {\lfloor\frac{n}{d}\rfloor}\frac{i}{2}(\sum _ {k|i} k\cdot\varphi(k)+1)\\ 其中i右边的式子可以调和级数O(n\lg n)求出，乘上i前缀和即可预处理出\sum _ {i=1} ^ {\lfloor\frac{n}{d}\rfloor}\frac{i}{2}(\sum _ {k|i} k\cdot\varphi(k)+1)\\ 将其记为f(\lfloor\frac{n}{d}\rfloor),则原式=\sum _ {d=1} ^ {n} d^2\cdot f(\lfloor\frac{n}{d}\rfloor),显然可以数论分块,但500000数据范围过大，考虑将f看作差分，对其求前缀和$$

const int maxN=555555,maxn=500000;
int n,T,phi[maxN],prime[maxN],tot;
bool notprime[maxN];
void getf()
{
    phi[1]=1;
    notprime[1]=true;
    rep(i,2,maxn)
    {
        if (!notprime[i]) prime[++tot]=i,phi[i]=i-1;
        for (int j=1;j<=tot&&i*prime[j]<=maxn;j++)
        {
            notprime[i*prime[j]]=1;
            if (i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}
LL f[maxN];
unsigned g[maxN];
int main()
{
    getf();
    rep(i,1,maxn)
        for (int j=i;j<=maxn;j+=i) f[j]+=(LL)i*phi[i];
    rep(i,1,maxn) f[i]=f[i-1]+i*(f[i]+1)/2LL;
    rep(i,1,maxn) for (LL j=1;j*i<=maxn;j++) 
    {
        g[j*i]+=(LL)i*i*f[j];
        if (i*(j+1)<=maxn) g[i*(j+1)]-=(LL)i*i*f[j];
    }
    rep(i,1,maxn) g[i]+=g[i-1];
    read(T);
    int kase=0;
    while (T--)
    {
        read(n);
        printf("Case #%d: %u\n",++kase,(unsigned)g[n]);
    }
    return 0;
}

例10 HDU6428 Calculate

$$\sum _ {i=1} ^ a \sum _ {j=1} ^ b \sum _ {k=1} ^ c \varphi(\gcd(i,j^2,k^3))$$

解:

$$这种复合的式子首先考虑将里面的利用莫比乌斯反演提出\\ 原式=\sum _ {i=1} ^ a \sum _ {j=1} ^ b \sum _ {k=1} ^ c \sum _ {d|\gcd(i,j^2,k^3)}(\varphi\ast\mu)(d)\\ =\sum _ {d=1} (\varphi\ast\mu)(d)\sum _ {i=1} ^ a \sum _ {j=1} ^ b \sum _ {k=1} ^ c [d|\gcd(i,j^2,k^3)]，内层外移\\ =\sum _ {d=1} (\varphi\ast\mu)(d)\sum _ {i=1} ^ a [d|i]\sum _ {j=1} ^ b [d|j^2]\sum _ {k=1} ^ c[d|k^3]，显然\\ 到这里，我们发现前面的\varphi\ast\mu可以线性处理，后面的式子似乎没那么好做。将其单独拿出来考虑\\ 首先感受一下发现，似乎只要某个数是离散意义下的\sqrt[k] d的倍数，即是符合式子的\\ 用数学语言描述就是\sum _ {i=1} ^ x [d|i^k]中，d|i^k\Rightarrow 对于d的质因数分解，\prod _ {j} prime[j]^{\lceil\frac{a[j]}{k}\rceil}|i\\ 则\sum _ {i=1} ^ x [d|i^k]=\lfloor \frac{x}{\prod _ {j} prime[j]^{\lceil\frac{a[j]}{k}\rceil}}\rfloor\\ 设分母为f(d)，由于其积性，可以线性预处理$$

void get(const unsigned &n)
{
    notprime[1]=true;
    mp[1]=1;f2[1]=1;f3[1]=1;
    for (unsigned i=2;i<=n;i++)
    {
        if (!notprime[i])
        {
            prime[++tot]=i;
            mp[i]=i-2;
            f2[i]=f3[i]=i;
            cnt[i]=1;
        }
        for (unsigned j=1;j<=tot&&i*prime[j]<=n;j++)
        {
            unsigned now=i*prime[j];
            notprime[now]=true;
            if (i%prime[j]==0) 
            {
                cnt[now]=cnt[i]+1;
                unsigned temp=i/prime[j];
                if (temp%prime[j]) mp[now]=mp[temp]*sqr(prime[j]-1);
                else mp[now]=mp[i]*prime[j];
                f2[now]=f2[i]*(cnt[now]&1?prime[j]:1);
                f3[now]=f3[i]*(cnt[now]%3==1?prime[j]:1);
                break;
            }
            cnt[now]=1;
            mp[now]=mp[i]*mp[prime[j]];
            f2[now]=f2[i]*f2[prime[j]];
            f3[now]=f3[i]*f3[prime[j]];
        }
    }
}//用unsigned是因为这道题的模数