积性函数（莫比乌斯）

一、莫比乌斯

1、莫比乌斯函数：\(u(n)=\left\{\begin{array}{l} 1\qquad \qquad n=1 \\ 0\qquad \qquad n含有平方因子 \\ (-1)^{k} \qquad n里面所包含质因子数目 \end{array}\right.\)

令 \(\varepsilon(n) = \sum_{d|n}^{n}u(d)=[n=1]\)，那么我们有 \(\varepsilon = u \ * \ 1\) ，当 \(n=1\) 时，\(\varepsilon (1) = 1\)，否则 \(\varepsilon (n) = 0\)。

定义：莫比乌斯是一个积性函数，积性函数乘以一个积性函数得到的函数也是一个积性函数，满足 \(h(x)=f(x)g(x)\)，另外也有如果\(gcd(n,m)=1\)，\(h(nm)=h(n)h(m)\) 。

此外完全积性函数满足任意的 \(h(nm)=h(n)h(m)\) 。

另外也有 \([gcd(i,j)=1]=\sum_{d|gcd(i,j)}u(d)=\varepsilon(gcd(i,j))\) 。

代码：线性筛预处理每个数的莫比乌斯函数值 \(O(n)\)

template<typename T>
struct Mu{
    int N;
    vector<T> preim;
    vector<T> a, mu;
    Mu(int N_) : a(N_ + 1), mu(N_ + 1) {
        N = N_;
        mu[1] = 1;
        for (T i = 2; i <= N; i++) {
            if (!a[i]) {
                a[i] = i;
                preim.push_back(i);
                mu[i] = -1;
            }
            for (auto p : preim) {
                if (1LL * i * p > N) continue;
                a[i * p] = p;
                if (i % p == 0) {
                    break;
                }
                mu[i * p] = -mu[i];
            }
        }
    }
};

2、扩展积性函数：

\(\varphi * 1=id\)

然后我们可以发现，我们对等式两边同时卷积 \(u\) ，得到 \(\varphi * 1 * u=id*u\Rightarrow \varphi*\varepsilon =id*u\Rightarrow\varphi=id*u\) 。

因此可以得到：\(\varphi(n)=\sum_{d|n}d·u(\frac{n}{d})\) 。

通常如果一个函数满足积性函数的性质，那么我们就能在线性筛的过程中 \(O(n)\) 的求出所有的函数值。

3、莫比乌斯变换：

\((1)\) ：形式一：如果有 \(f(n)=\sum_{d|n}g(d)\)，那么有 \(g(n)=\sum_{d|n}f(d)u(\frac{n}{d})\) 。

\((2)\) ：形式二：如果有 \(f(n)=\sum_{n|d}g(d)\)，那么有 \(g(n)=\sum_{n|d}f(d)u(\frac{d}{n})\) 。

通常情况下第二种形式常用。

4、有一些做题出现的常见的式子：

\((1)\)：\(\sum_{i=x}^{n}\sum_{j=y}^{m}[gcd(i,j)=k]\qquad (1 \le T,x,y,n,m,k\le 5e4)\) 。

我们令 \(f(x,n,y,m)=\sum_{i=x}^{n}\sum_{j=y}^{m}[gcd(i,j)=k]\qquad (1 \le T,x,y,n,m,k\le 5e4)\)，那么我们可以由容斥定理得：\(f(x,n,y,m)=f(1,n,1,m)-f(1,x-1,1,m)-f(1,n,1,y-1)+f(1,x-1,1,y-1)\)，所以相当于分为四个部分进行处理 。

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

\(\Rightarrow \sum_{i=1}^{\frac{n}{k}}\sum_{i=1}^{\frac{m}{k}}\sum_{d|gcd(i,j)}u(d)\)

\(\Rightarrow \sum_{d=1}^{\frac{min(n,m)}{k}}u(d)\sum_{i=1}^{\frac{n}{k}}[d\ |\ i]\sum_{i=1}^{\frac{m}{k}}[d\ |\ j]\)

\(\Rightarrow \sum_{d=1}^{\frac{min(n,m)}{k}}u(d)\left \lfloor \frac{n}{dk} \right \rfloor\left \lfloor \frac{m}{dk} \right \rfloor\)

然后就可以把上面的公式套入这里面，得到答案。

时间复杂度为：\(O(T\sqrt{n})\) 。

\((2)\)：\(\sum_{i=1}^{n}lcm(i,n)\qquad 1\le T\le 3e5,1\le n\le1e6\) 。

\(\Rightarrow \sum_{i=1}^{n}\frac{in}{gcd(i,n)}\)

\(\Rightarrow n\sum_{d|n}\frac{1}{d}\sum_{i=1}^{n}i[gcd(i,n)=d]\)

\(\Rightarrow n\sum_{d|n}\sum_{i=1}^{\frac{n}{d}}i[gcd(i,\frac{n}{d})=1]\)

\(\Rightarrow n\sum_{d|n}\sum_{i=1}^{\frac{n}{d}}i\sum_{k|gcd(i,\frac{n}{d})}u(k)\)

\(\Rightarrow n\sum_{d|n}\sum_{k|\frac{n}{d}}u(k)\sum_{i=1}^{\frac{n}{d}}i[k|i]\)

我们令 \(sum(x)=(1+2+...x)=(1+x)*x/2\)，那么

\(\Rightarrow n\sum_{d|n}\sum_{k|\frac{n}{d}}k·u(k)sum(\left \lfloor \frac{n}{dk} \right \rfloor)\)

现在我们令 \(T=dk\)，那么有：

\(n\sum_{T|n}sum(\left \lfloor \frac{n}{dk} \right \rfloor)\sum_{k|T}k·u(k)\)

可以看出我们可以在时间复杂度为 \(O(nlogn)\) 下预处理出 \(1-n\) 里面的所有值。

另外的推导：

\(\sum_{i=1}^{n}\frac{i·n}{gcd(i,n)}=\frac{1}{2}(\sum_{i=1}^{n-1}\frac{i·n}{gcd(i,n)}+\sum_{i=n-1}^{1}\frac{i·n}{gcd(i,n)})+n\)

又由于 \(gcd(i,n)=gcd(n-i,n)\)

所以有 \(\frac{1}{2}(\sum_{i=1}^{n-1}\frac{i·n}{gcd(i,n)}+\sum_{i=n-1}^{1}\frac{i·n}{gcd(n-i,n)})+n=\frac{1}{2}\sum_{i=1}^{n-1}\frac{n^2}{gcd(i,n)}+n=\frac{1}{2}\sum_{i=1}^{n}\frac{n^2}{gcd(i,n)}+\frac{n}{2}\) 。

然后有：\(\sum_{i=1}^{n}\frac{n^2}{gcd(i,n)}=n^{2}\sum_{d|n}\frac{1}{d}\sum_{i=1}^{n}[gcd(i,n)=d]=n^2\sum_{d|n}\frac{1}{d}\sum_{i=1}^{\frac{n}{d}}[gcd(i,\frac{n}{d})=1]=n^2\sum_{d|n}\frac{1}{d}\varphi (\frac{n}{d})=\sum_{d|n}\frac{n^2\varphi (\frac{n}{d})}{d}\) 。

所以得到原式可以化简为：\(\frac{n}{2}(\sum_{d'|n}d'\varphi (d')+1)\)

现在我们可以看出我们可以在 \(O(nlog n)\) 的时间复杂度预处理出所有值。

不过 我们令 \(f(x)=\sum_{d|x}d\varphi(d)\)，可以发现 \(f(x)\) 是一个积性函数，我们可以通过线性筛的形式 \(O(n)\) 预处理出所有值。

推导：\(f(p^k)=\sum_{w=0}^{k}p^w\varphi(p^w)=\sum_{w=0}^kp^{2w-1}(p-1)\)，则 \(f(p^{k+1})=f(p^k)+p^{2k+1}(p-1)\) 。

如果 \(p|i\)，则令 \(i=a·p^w \ (gcd(a,p)=1)\)，得到 \(f(i*p)=f(a)f(p^{w+1})\)、\(f(i)=f(a)f(p^w)\) 。

则 \(f(i*p)-f(i)=f(a)*(f(p^{w+1})-f(p^w))=f(a)*p^{2w+1}(p-1)\)，同理得到 \(f(i)-f(\frac{i}{p})=f(a)*(f(p^w)-f(p^{w-1}))=f(a)*p^{2w-1}(p-1)\) 。

因此得到 \(f(i*p)=f(i)+(f(i)-f(\frac{i}{p}))*p^2\) 。

时间复杂度为：\(O(n)\) 。

\((3)\)：\(\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j) \qquad (n,m \le 1e7)\)

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

我们先令 \(sum(x)=(1+2+...x)=(1+x)*x/2\)

我们令 \(f(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m}i·j\sum_{k|gcd(i,j)}u(k)=\sum_{k=1}^{min(n,m)}u(k)\sum_{i=1}^{n}i[k|i]\sum_{j=1}^{m}j[k|j]=\sum_{k=1}^{min(n,m)}u(k)k^2sum(\left \lfloor \frac{n}{k} \right \rfloor)sum(\left \lfloor \frac{m}{k} \right \rfloor)\)

则最后要求的答案为：\(\sum_{d=1}^{min(n,m)}f(\frac{n}{d},\frac{m}{d})\) ，得解。

\((4)\)：约数个数和：\(\sum_{i=1}^{n}\sum_{j=1}^{m}d(i·j) \qquad (n,m,T \le 5e4)\) 。

其中 \(d(x)\) 表示 \(x\) 的约数个数，这里需要用到 \(d(x)\) 的一个性质。