从积性函数到莫比乌斯反演

呜呜呜，为了数论课不做大牢，学数论！

简单介绍

数论函数

数论函数，简单来说就是定义域是$\mathbb{N^{*}}$的函数，可以视为一个数列

积性函数

定义

积性函数是一类特殊的数论函数，它满足以下性质
$$
f(1) = 1.\ \forall i, j\in\mathbb{N^{}},gcd(i,j)=1: f(ij)=f(i)*f(j)
$$
特别的

若积性函数被称为完全积性函数，若它满足以下性质
$$
\forall i,j\in \mathbb{N^{}}:f(ij)=f(i)*f(j)
$$

性质

设$f$,$g$为积性函数，则
$$
h(x)=f(x)*g(x),\
h(x)=f(x^{p}),\
h(x)=f^{p}(x),\
h(x)=\sum_{d|x}f(d)g(\frac{x}{d})
$$
也为积性函数

特别的，根据唯一分解定理，设$x=\prod p_i^{k_i}$，若$F$为积性函数，则有
$$
F(x)=\prod F(p_i^{k_i})
$$
若$F$为完全积性函数，则有
$$
F(x)=\prod F^{k_i}(p_i)
$$

例子

恒等函数$id(n) \equiv n$

单位函数$\epsilon (n)=[n=1]$

常数函数$1(n)\equiv 1$

因子和函数$\delta(n)=\sum_{d|n}d$

因子个数函数$\tau(n)=\sum_{d|n}1$

一般的，除数函数$\sigma_k(n)=\sum_{d|n}d^k$

欧拉函数$\phi(n)=\sum_{i=1}^n[gcd(i,n)=1]$，即$n$的与$n$互质的因数的个数

莫比乌斯函数，其中$n=\prod_{i=1}^r p_i^{k_i}$
$$
\mu(n)=\begin{cases}
1,n=1\
0,\exists i, s.t.k_i>=2\
(-1)^r,otherwise
\end{cases}
$$
值得指出的是，上述前三个函数为完全积性函数

$Dirichlet$卷积

定义

设$f$和$g$为数论函数，则两者的$Dirichlet$卷积$fg$定义如下
$$
fg(n):=\sum_{d|n}f(d)g(\frac{n}{d})
$$

性质

$f$,$g$,$h$为数论函数

单位元存在性

$\forall f, \exists \epsilon :f*\epsilon \equiv f$

逆元唯一性

若$\exists g, s.t.f*g\equiv\epsilon$，则称$g$为$f$的逆元，事实上，逆元唯一

交换律

$fg=gf$

结合律

$f*(gh)=(fg)*h$

分配律

$f*(g+h)=fg+fh$

恒等关系

$f=g\iff fh=gh$

重要结论

1.积性函数的卷积仍为积性函数

2.积性函数的逆元也为积性函数

例子

1.$\epsilon=\mu*1$

2.$\tau=1*1$

3.$\delta=id*1$

4.$\phi=\mu*n$

数论分块

数论分块可以用于快速求解带向下取整（显然也有整除）的和式，时间复杂度可以达到$O(\sqrt n)$

两个结论

1.$\forall a,b,c\in\mathbb{Z}, \lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor=\lfloor\frac{a}{bc}\rfloor$

2.$\forall n\in\mathbb{N^*},|V|={\lfloor\frac{n}{d}\rfloor|\forall d, 1 \le d\le n}| \le 2\lfloor\sqrt{n}\rfloor$

所以可以枚举每个整数$d$对应的$i$的区间，来分块计算各个小区间对应的答案，最后相加就行，实现如下

实现

ll partitioning(ll n) {
    ll ans = 0;
    ll l, r;
    for(l = 1; l <= n; l++) {
        r = n / (n / l);
        ans += 1LL * (r - l + 1) * expression(l);\\expression is the formula that is to be solved
        l = r;
    }
    return ans;
}

莫比乌斯反演

来到了，高一集训时的噩梦，$cjq$大仙的解方程猜测$\mu$函数现场，四年来念念不忘的Mobius Inversion

$\mu$函数的补充

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

即$[gcd(i,j)=1]=\epsilon *gcd(i,j)$

显然，如果$gcd(i,j)=1$，那么d只能取$1$，故和式为$1$；若不然，$gcd(i,j)$的因子总是成对出现，故可取到的$\mu$中$(-1)^r$的$r$总是连续的$1-2n$，故结果为$0$

线性筛

线性筛可以用于求绝大部分积性函数（其实我也不知道有什么不能求的），区别只在于在线性筛过程中对函数值的处理计算

对于$\mu$函数，实现如下

实现

void getMu() {
    mu[1] = 1;
    inp[1] = 1;
    for(int i = 2; i <= maxn; i++) {
        if(!inp[i]) prime[++tot] = i, mu[i] = -1;
        for(int j = 1; j <= tot && i * prime[j] <= maxn; j++) {
            inp[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                mu[i * p[j]] = 0;
                break;
            }
            mu[i * p[j]] = -mu[i];
        }
    }
}

结论

$f$和$g$为两个数论函数，若
$$
f(n)=\sum_{d|n}g(d)
$$
则有
$$
g(n)=\sum_{d|n}\mu(d)f(\frac{n}{d})
$$
$f$称为$g$的莫比乌斯变换，$而g$称为$f$的莫比乌斯反演，可以看出，$f = g*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_{d=1}\mu(d)\sum_{i = 1}^n[d|i]\sum_{j=1}^m[d|j]
$$
显然后面两个求和号可以直接得出结果，故
$$
\sum_{i=1}^n\sum_{j=1}^m [gcd(i,j)=1]=\sum_{d=1}^{min(n,m)}\mu(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor
$$
直接使用数论分块解决即可

实现

以[HAOI2011] Problem b为例

推导与上述无异，再使用二维容斥即可解决问题

即计算
$$
\sum_{d=1}^{min(\lfloor\frac{n}{k}\rfloor,\lfloor\frac{m}{k}\rfloor)}\mu(d)\lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor
$$
令$n=b,m=d;n=b,m=c-1;n=a-1,m=d;n=a-1,m=c-1$四种情况即可

int n, mu[maxn], prime[maxn], tot = 0;
bool inp[maxn];
int a, b, c, d, k;

void init() { //get prefix of mu
    mu[1] = 1, inp[1] = 1;
    rep(i, 2, maxn) {
        if(!inp[i]) {
            prime[++tot] = i;
            mu[i] = -1;
        }
        for(int j = 1; j <= tot && i * prime[j] <= maxn; j++) {
            inp[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                mu[i * prime[j]] = 0;
                break;
            }
            mu[i * prime[j]] = -mu[i];
        }
    }
    rep(i, 1, maxn) mu[i] += mu[i - 1];
}

ll cal(int n, int m) { //calculate the sum
    ll ans = 0;
    ll l, r;
    for(l = 1; l <= min(n, m); l++) {
        r = min(n / (n / l), m / (m / l));
        ans += 1LL * (mu[r] - mu[l - 1]) * (n / l) * (m / l);
        l = r;
    }
    return ans;
}

void solve() {
    a = read(), b = read(), c = read(), d = read(), k = read();
    ll res = cal(b / k, d / k) - cal((a - 1) / k, d / k) - cal(b / k, (c - 1) / k) + cal((a - 1) / k, (c - 1) / k);
    printf("%lld\n", res);
}