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

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

简单介绍

数论函数

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

积性函数

定义

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

若积性函数被称为完全积性函数，若它满足以下性质 \[ \forall i,j\in \mathbb{N^{*}}:f(i*j)=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\)卷积\(f*g\)定义如下 \[ f*g(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\)的逆元，事实上，逆元唯一

交换律

\(f*g=g*f\)

结合律

\(f*(g*h)=(f*g)*h\)

分配律

\(f*(g+h)=f*g+f*h\)

恒等关系

\(f=g\iff f*h=g*h\)

重要结论

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);
}