竞赛算法(4) 数论

数论基础#

整除#

具有如下基础性质:

$a | b$ 则 $-a | b$ , $a | -b$
$a | b$ , $b | c$ 则 $a | c$
$a | b$ , $a | c$ 则 $a | xb + yc$
$a | b$ , $b | a$ 则 $b = a$ 或 $b = -a$
$a | b$ 则 $ma | mb(m\ne0)$ .
$a | b$ , $b\ne0$ 则 $|a| \le |b|$
$a | b$ 则 $a | b\% a$

有上述性质可知整除是整数集上的偏序关系. 若a整除b, 则称a为b的约数, b为a的倍数.

0, 1, -1, b, -b称为平凡约数, 其他约数称为真约数.

若 $b\ne0$ , 当 $d$ 遍历 $b$ 的全体约数时, $b/d$ 也遍历 $b$ 的全体约数.

带余除法#

$b = (b / a)a + b \% a$ .

相邻的 a 个整数被正整数 a 除后, 恰好取到上述 a 个余数. 特别地, 一定有且仅有一个数被 a 整除.

gcd与lcm#

gcd有如下性质:

gcd(a, b) = gcd(-a, b), 正负不影响结果
gcd(a, b) = gcd(b, a), 可交换
gcd(a, 0) = gcd(a, a) = abs(a)
gcd(bq + r, b) = gcd(r, b)
gcd(a, b, c) = gcd(gcd(a, b), c), 可结合
gcd(a, b, c...) * m = gcd(ma, mb, mc...)
gcd(a^n, b^n) = gcd(a, b)^n
若gcd(a, b, c...) = d, 则gcd(a / d, b / d, c / d...) = 1
若a | bc, a, b互质, 则a | c.
若a | c, b | c, a, b互质, 则ab | c.
若a, b互质, 则gcd(a, bc) = gcd(a, c)
若A, B数组组间两两互质, 即任意a, b互质, 则mul(A), mul(B)互质.
若互质的n个数相乘等于某个数v的m次方, 则这n个数每个都是完全m次方数.

lcm有如下性质:

同gcd
同gcd
同gcd
若a | b, 则lcm(a, b) = b
可结合
同gcd
若数组A每个数a都有a | m, 则lcm(A) | m.
lcm(a, b, c)lcm(ab, bc, ca) = lcm(a, b)lcm(b, c)lcm(a, c)
lcm(a^n, b^n) = lcm(a, b)^n

有一些奇怪的等式:

gcd(a, b)lcm(a, b) = ab
gcd(ab, bc, ca)lcm(a, b, c) = abc
gcd(a, b, c)gcd(a, b, c) / gcd(a, b)gcd(a, c)gcd(b, c) = lcm[a, b, c]lcm[a, b, c] / lcm(a, b)lcm(a, c)lcm(b, c)

质数#

所有大于3的素数都可以表示为6n + 1或6n + 5的形式.

算术基本定理#

算术基本引理: 若p为素数, p | xy, 则要么p | x, 要么p | y. 算术基本定理/唯一分解定理: a可被唯一的素数数组P表示, a = mul(P) 这两个定理等价.

同余#

若m | (a - b)称a, b模m同余, 记作 $a\equiv b\pmod m$ 同余是一种等价关系. 同余的性质:

自反, 对称, 传递
线性运算(加减乘)
若两个整系数多项式的所有系数模m同余, 则这两个多项式模m同余意义下等价. (对于任意s, t模m同余, f(s)与g(t)模m同余)
a, b模m同余, 则ak, bk模mk同余. 若k整除a, b, m, 则反过来也一样.
若d | m, a, b模m同余, 则a, b模d同余.
若a, b模m同余, 则gcd(a, m) = gcd(b, m).
若a, b模m同余, d | m且d | a, 则d | b.

同余类与剩余系#

模运算算法#

模运算环#

1
namespace numth {
2
    inline ll norm(ll x, ll mod) { ll tmp = x % mod; return (tmp < 0) ? (tmp + mod) : tmp; }
3
    inline ll mul(ll a, ll b, ll mod) { auto tmp = (i128)a * b % mod; return (tmp < 0) ? (tmp + mod) : tmp; }
4
    inline ll add(ll a, ll b, ll mod) { return norm(a + b, mod); }
5
    inline ll sub(ll a, ll b, ll mod) { return norm(a - b, mod); }
6
    inline ll pow(ll a, ll b, ll mod) {
7
        ll ret = 1;
8
        a = norm(a, mod);
9
        for (; b; b >>= 1, a = mul(a, a, mod)) if (b & 1) ret = mul(ret, a, mod);
10
        return ret;
11
    }
12
    inline ll inv(ll a, ll mod_prime) { return pow(a, mod_prime - 2, mod_prime); }
13
}

在模数为质数的情况下, 模运算构成一个环. norm: 模. 模运算的结果总是在[0, mod)之间.

模整数类#

代码比模运算环更长, 但健壮性更好(支持合数模数), 且速度更快. 静态u32(最快):

1
template <int MOD>
2
struct modint {
3
    static constexpr u32 umod = u32(MOD);
4
    static constexpr int mod = MOD;
5
    static constexpr int get_mod() { return mod; }
6
    static_assert(umod < u32(1) << 31);
7
    u32 val;
8

9
    // fast construction of raw modint
10
    static modint raw(u32 v) {
11
        modint x;
12
        x.val = v;
13
        return x;
14
    }
15

16
    // constructors
17
    constexpr modint() : val(0) {}
18
    constexpr modint(u32 x) : val(x % umod) {}
19
    constexpr modint(u64 x) : val(x % umod) {}
20
    constexpr modint(u128 x) : val(x % umod) {}
21
    constexpr modint(int x) : val((x %= mod) < 0 ? x + mod : x) {};
22
    constexpr modint(ll x) : val((x %= mod) < 0 ? x + mod : x) {};
23
    constexpr modint(i128 x) : val((x %= mod) < 0 ? x + mod : x) {};
24

25
    // operators
26
    bool operator<(const modint &other) const { return val < other.val; }
27
    modint &operator+=(const modint &p) {
28
        if ((val += p.val) >= umod) {
29
            val -= umod;
30
        }
31
        return *this;
32
    }
33
    modint &operator-=(const modint &p) {
34
        if ((val += umod - p.val) >= umod) {
35
            val -= umod;
36
        }
37
        return *this;
38
    }
39
    modint &operator*=(const modint &p) {
40
        val = u64(val) * p.val % umod;
41
        return *this;
42
    }
43
    modint &operator/=(const modint &p) {
44
        // O(log mod)
45
        assert(p.val != 0 && "modint div zero");
46
        *this *= p.inv();
47
        return *this;
48
    }
49
    modint operator-() const { return modint::raw(val ? mod - val : u32(0)); }
50
    modint operator+(const modint &p) const { return modint(*this) += p; }
51
    modint operator-(const modint &p) const { return modint(*this) -= p; }
52
    modint operator*(const modint &p) const { return modint(*this) *= p; }
53
    modint operator/(const modint &p) const { return modint(*this) /= p; }  // O(log mod)
54
    bool operator==(const modint &p) const { return val == p.val; }
55
    bool operator!=(const modint &p) const { return val != p.val; }
56

57
    // quick power of O(log n)
58
    modint qkpow(ll n) const {
59
        if (n < 0) return inv().qkpow(-n);
60
        modint ret(1), mul(val);
61
        while (n > 0) {
62
            if (n & 1) ret *= mul;
63
            mul *= mul;
64
            n >>= 1;
65
        }
66
        return ret;
67
    }
68

69
    // inv by extgcd of O(log mod)
70
    modint inv() const {
71
        // no inv for zero, no inv for non-coprime
72
        assert(val != 0 && "modint inv zero");
73
        assert((gcd((int)val, mod) == 1) && "modint inv not coprime");
74

75
        int a = val, b = mod, u = 1, v = 0, t;
76
        while (b > 0) {
77
            t = a / b;
78
            swap(a -= t * b, b), swap(u -= t * v, v);
79
        }
80
        return modint(u);
81
    }
82

83
    // stream IO
84
    friend std::istream &operator>>(std::istream &is, modint &a) {
85
        ll t;
86
        is >> t;
87
        a = modint(t);
88
        return is;
89
    }
90
    friend std::ostream &operator<<(std::ostream &os, const modint &a) {
91
        return os << a.val;
92
    }
93
};
94
using mint107 = modint<1000000007>;
95
using mint998 = modint<998244353>;

O2有自动Barrett优化, 而且不涉及i128, 常数非常小. 且支持所有常见运算. 无依赖.

Barrett算法#

1
struct Barrett {
2
    u32 m;
3
    u64 im;
4
    explicit Barrett(u32 m = 1) : m(m), im(u64(-1) / m + 1) {}
5
    u32 umod() const { return m; }
6
    u32 modulo(u64 z) {
7
        if (m == 1) return 0;
8
        u64 x = (u64)(((unsigned __int128)(z)*im) >> 64);
9
        u64 y = x * m;
10
        return (z - y + (z < y ? m : 0));
11
    }
12
    u64 floor(u64 z) {
13
        if (m == 1) return z;
14
        u64 x = (u64)(((unsigned __int128)(z)*im) >> 64);
15
        u64 y = x * m;
16
        return (z < y ? x - 1 : x);
17
    }
18
    pair<u64, u32> divmod(u64 z) {
19
        if (m == 1) return {z, 0};
20
        u64 x = (u64)(((unsigned __int128)(z)*im) >> 64);
21
        u64 y = x * m;
22
        if (z < y) return {x - 1, z - y + m};
23
        return {x, z - y};
24
    }
25
    u32 mul(u32 a, u32 b) { return modulo(u64(a) * b); }
26
};

模整数类(动态)#

基于手写Barrett算法. 支持u32范围内的模数(更大的模数需要手写Barrett64和Dynamic_modint64)

1
template <int id>
2
struct Dynamic_Modint {
3
    static constexpr bool is_modint = true;
4
    using mint = Dynamic_Modint;
5
    u32 val;
6
    static Barrett bt;
7
    static u32 umod() { return bt.umod(); }
8

9
    static int get_mod() { return (int)(bt.umod()); }
10
    static void set_mod(int m) {
11
        assert(1 <= m);
12
        bt = Barrett(m);
13
    }
14

15
    static Dynamic_Modint raw(u32 v) {
16
        Dynamic_Modint x;
17
        x.val = v;
18
        return x;
19
    }
20
    Dynamic_Modint() : val(0) {}
21
    Dynamic_Modint(u32 x) : val(bt.modulo(x)) {}
22
    Dynamic_Modint(u64 x) : val(bt.modulo(x)) {}
23
    Dynamic_Modint(int x) : val((x %= get_mod()) < 0 ? x + get_mod() : x) {}
24
    Dynamic_Modint(ll x) : val((x %= get_mod()) < 0 ? x + get_mod() : x) {}
25
    Dynamic_Modint(i128 x) : val((x %= get_mod()) < 0 ? x + get_mod() : x){};
26

27
    mint& operator+=(const mint& rhs) {
28
        val = (val += rhs.val) < umod() ? val : val - umod();
29
        return *this;
30
    }
31
    mint& operator-=(const mint& rhs) {
32
        val = (val += umod() - rhs.val) < umod() ? val : val - umod();
33
        return *this;
34
    }
35
    mint& operator*=(const mint& rhs) {
36
        val = bt.mul(val, rhs.val);
37
        return *this;
38
    }
39
    mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
40
    mint operator-() const { return mint() - *this; }
41
    mint pow(ll n) const {
42
        assert(0 <= n);
43
        mint x = *this, r = 1;
44
        while (n) {
45
            if (n & 1) r *= x;
46
            x *= x, n >>= 1;
47
        }
48
        return r;
49
    }
50
    mint inv() const {
51
        int x = val, mod = get_mod();
52
        int a = x, b = mod, u = 1, v = 0, t;
53
        while (b > 0) {
54
            t = a / b;
55
            swap(a -= t * b, b), swap(u -= t * v, v);
56
        }
57
        if (u < 0) u += mod;
58
        return u;
59
    }
60

61
    friend mint operator+(const mint& lhs, const mint& rhs) { return mint(lhs) += rhs; }
62
    friend mint operator-(const mint& lhs, const mint& rhs) { return mint(lhs) -= rhs; }
63
    friend mint operator*(const mint& lhs, const mint& rhs) { return mint(lhs) *= rhs; }
64
    friend mint operator/(const mint& lhs, const mint& rhs) { return mint(lhs) /= rhs; }
65
    friend bool operator==(const mint& lhs, const mint& rhs) { return lhs.val == rhs.val; }
66
    friend bool operator!=(const mint& lhs, const mint& rhs) { return lhs.val != rhs.val; }
67
};
68

69
using dmint = Dynamic_Modint<-1>;
70
template <int id>
71
Barrett Dynamic_Modint<id>::bt;

数论函数#

正整数到整数(在广义数论中可以是复数)的函数. 可以被看作一个数列.

积性函数#

$f(1) = 1$ .
对于互质的 $x$ , $y$ , 有 $f(xy) = f(x)f(y)$ .

完全积性函数

$f(1) = 1$ .

对于任意的 $x$ 与 $y$ , 有 $f(xy) = f(x)f(y)$ .

积性函数的性质
若 $f(x), g(x)$ 都是积性函数:

$f(x^p)$ 也是积性函数.

$f^p(x)$ 也是积性函数.

$f(x)g(x)$ 也是积性函数.

$\displaystyle \sum _{d|x}f(d)g(\frac{x}{d})$ 也是积性函数.

容易注意到正整数在唯一分解后, 积性函数等于其每一个质因数幂次的函数值相乘, 完全积性函数还等于其每一个质因数的函数值相乘.

常见的积性函数

单位函数 $\epsilon (n) = [n = 1].$ 即 $n = 1$ 的指示函数. 为完全积性函数.

恒等函数 $id_k(n) = n^k, id(n) = n$ . 完全积性.

常数函数 $1(n) = 1$ . 完全积性.

除数函数 $\displaystyle \sigma _k(n) = \sum _{d|n}d^k$ . 其中 $\sigma _0(n)$ 常记作 $d(n)$ 或 $\tau(n)$ , $\sigma_1(n)$ 常记作 $\sigma(n)$ .

欧拉函数 $\varphi(n) = \displaystyle\sum_{i = 1}^{n}[gcd(i, n) = 1]$ .

莫比乌斯函数 $\mu (n)$ . $n$ 为 $1$ 时值为 $1$ , $n$ 为完全平方数的整数倍时值为 $0$ , 其他时候值为 $(-1)^k$ , 其中 $k$ 为 $n$ 的不相等质因子个数.

欧拉函数#

一种数论函数, 记作 $\varphi(n)$ , 是一种积性函数, 其含义为小于等于n的正整数中与n互质的数的个数.

欧拉函数的性质

欧拉函数是积性函数. 特别地, 当 $n$ 为奇数时, $\varphi(2n) = \varphi(n)$ .

$n = \displaystyle\sum_{d|n}\varphi(d)$ . 即恒等函数 $id$ 是常数函数 $1$ 和欧拉函数 $\varphi$ 的狄利克雷卷积.

若 $n = p^k$ , 则 $\varphi(n) = p^k - p^{k - 1}$ .

$\varphi(n)$ 等于 $n$ 除以所有不同的质因数, 再乘以所有不同质因数-1的结果.

莫比乌斯函数#

一种数论函数, 记作 $\mu(n)$ :

$n = 1$ 时 $\mu(n) = 1$ .
$n$ 的质因数分解形如 $p_1p_2p_3\cdots p_k$ , 其中 $p_i$ 之间互不相等时, $\mu(n) = (-1)^k$ .
其他时候, $\mu(n) = 0$ .

莫比乌斯函数是一种积性函数.

莫比乌斯函数可以使用质因数分解在 $O(\sqrt{n})$ 时间内求出. 也可使用线性筛在 $O(n)$ 时间内预处理出 $1\sim n$ 内所有的莫比乌斯函数值.

欧拉筛#

一种 $O(n)$ 的筛法, 也叫线性筛.

:::[欧拉筛处理质数的过程]

维护质数表primes(要求支持 $O(1)$ 尾插), 最小质因数表minp.
循环, 到i时(先判后筛):
1. 判: 若minp[i] == 0, 说明没被筛过, 为质数. minp[i] = i, primes尾插i.
2. 筛: 遍历所有小于等于minp[i]的质数pj. 我们考虑i * pj, 可以知道pj一定是i * pj的最小质因数(由唯一分解定理). 于是记录minp[i * pj] = pj, 表示i * pj已经被筛过. :::

这个过程中, minp可以换成一个bool数组vis以节省空间, 这样的话筛的时候条件改为”从小到大遍历所有i % pj != 0的质数和第一个i % pj == 0的质数”. 常数时间接近, 空间节省, 但缺少了副产物minp表.

欧拉筛用于预处理 $\varphi(n)$ , $\mu(n)$ , $d(n)$ , $\sigma(n)$ 等特殊积性函数时, 利用其特殊性质可以避开处理一般积性函数时较差的时空复杂度.

1
using i8 = int8_t;
2
using ll = long long;
3
// 全局
4
int minp[N];        // minp[i]反映i的最小质因数
5
/*
6
int phi[N], d[N];
7
i8 mu[N];
8
int times[N];       // 求d用, 表示最小质因子的次数.
9

10
ll sigma[N];
11
int g[N];           // 求sigma用, 表示最小质因子的幂次贡献的约数和.
12
*/
13

14
// 局部
15
vector<int> primes; // 质数表, primes[0] = 2
16
auto euler = [&](int n) -> void {
17
    primes.clear();
18
    memset(minp, 0, sizeof(int) * (n + 3));
19
    /*
20
    memset(phi, 0, sizeof(int) * (n + 3));
21
    memset ... 以下省略
22

23
    phi[1] = mu[1] = d[1] = sigma[1] = 1;
24
    */
25
    for (int i = 2; i <= n; i++) {
26
        if (minp[i] == 0) {
27
            primes.push_back(i);
28
            minp[i] = i;
29
            /*
30
            phi[i] = i - 1;
31

32
            mu[i] = -1;
33

34
            d[i] = 2;
35
            times[i] = 1;
36

37
            sigma[i] = i + 1;
38
            g[i] = i + 1;
39
            */
40
        }
41
        for (const auto& pj : primes) {
42
            if (pj > minp[i] || pj > n / i) break;
43
            /*
44
            if (pj == minp[i]) {
45
                phi[i * pj] = phi[i] * pj;
46

47
                mu[i * pj] = 0;
48

49
                d[i * pj] = d[i] / (times[i] + 1) * (times[i] + 2);
50
                times[i * pj] = times[i] + 1;
51

52
                g[i * pj] = g[i] * pj + 1;
53
                sigma[i * pj] = sigma[i] / g[i] * g[i * pj];
54
            }
55
            else {
56
                phi[i * pj] = phi[i] * (pj - 1);
57

58
                mu[i * pj] = -mu[i];
59

60
                d[i * pj] = d[i] * 2;
61
                times[i * pj] = 1;
62

63
                sigma[i * pj] = sigma[i] * sigma[pj];
64
                g[i * pj] = pj + 1;
65
            }
66
            */
67
            minp[i * pj] = pj;
68
        }
69
    }
70
};
71

72
// 判定质数
73
auto isprime = [&](int x) -> bool {
74
    return x == minp[x];
75
};

欧拉筛求一般积性函数#

若可以在关于 $k$ 的低次多项式时间(在算法竞赛中, 可以忽略”低次”, 因为 $k$ 可以看作常数)内得到积性函数 $f$ 在 $p^k$ 处的值(其中 $p$ 为质数), 便可在 $O(n)$ 内使用线性筛预处理出 $1\sim n$ 范围内所有的 $f(n)$ 值.

欧拉筛预处理积性函数的过程

维护质数表primes( $O(1)$ 尾插). <int>minp或<bool>vis用于标记. low用于记录i的最小质因子的完整幂. f用于储存答案. 定义函数getf(int p, int pk)用于快速求 $f(p^k)$ . 初始化f[1] = 1, low[1] = 1.

循环, 到i时(先判后筛):

判: 若为质数, 更新4项(包括primes).

筛, 其实就是3个分支, (注意pj > n / i时要提前break):

pj < minp[i], 更新3项.

pj == minp[i], 更新low[tgt]和minp[tgt], 判断, 最后break:

i == low[i], 说明i是质数整幂, 调用getf;

i != low[i], 直接计算f.

1
// 全局
2
int minp[N], low[N];
3
ll f[N];
4

5
// 局部
6
vector<int> primes;
7
auto euler = [&](int n) -> void {
8
    primes.clear();
9
    memset(minp, 0, sizeof(int) * (n + 3));
10
    memset(low, 0, sizeof(int) * (n + 3));
11
    memset(f, 0, sizeof(int) * (n + 3));
12
    f[1] = 1, low[1] = 1;
13
    for (int i = 2; i <= n; i++) {
14
        if (minp[i] == 0) {
15
            primes.push_back(i);
16
            low[i] = i;
17
            minp[i] = i;
18
            f[i] = getf(i, i);
19
        }
20
        for (const auto& pj : primes) {
21
            if (pj > n / i) break;
22

23
            int tgt = pj * i;
24
            minp[tgt] = pj;
25
            if (pj != minp[i]) {
26
                low[tgt] = pj;
27
                f[tgt] = f[pj] * f[i];
28
            }
29
            else {
30
                low[tgt] = pj * low[i];
31
                if (i == low[i]) {
32
                    f[tgt] = getf(pj, low[tgt]);
33
                }
34
                else {
35
                    f[tgt] = f[tgt / low[tgt]] * f[low[tgt]];
36
                }
37
                break;
38
            }
39
        }
40
    }
41
}

预处理后快速分解质因数#

在预处理出minp数组后, 可以在 $O(\log n)$ 的时间内完成质因数的单次询问. 不断除以minp[i]即可.

1
vector<int> getfac(int x) {
2
    vector<int> ans;
3
    while (x > 1) {
4
        ans.push_back(minp[x]);
5
        x /= minp[x];
6
    }
7
    return ans;
8
}

整除分块(数论分块)#

在 $O(1)$ 得到 $f_{pre}$ 和 $g$ 的前提下, 以 $O(\sqrt{n})$ 的复杂度计算 $\displaystyle\sum_{i=1}^{limit}f(i)g(\lfloor \frac{n}{i}\rfloor)$ .

1
template <typename F>
2
void block_floor(ll N, F f) {
3
    ll sq = sqrtl(N);
4
    ll n = (sq * sq + sq <= N ? sq : sq - 1);
5
    for (ll l = 1; l <= sq; ++l) {
6
        f(N / l, l, l + 1);
7
    }
8
    for (ll q = n; q >= 1; --q) {
9
        f(q, N / (q + 1) + 1, N / q + 1);
10
    }
11
}

狄利克雷卷积#

数论函数 $f(n)$ 与 $g(n)$ 的狄利克雷卷积记作 $f*g$ , 定义为 $\displaystyle\sum_{k|n}f(k)g(\frac{n}{k}) = \sum_{kl=n}f(k)g(l)$ .

常见的狄利克雷卷积

单位函数 $\varepsilon$ 是默比乌斯函数 $\mu$ 和常数函数 $1$ 的狄利克雷卷积(莫比乌斯反演的核心): $\varepsilon = \mu * 1 \iff \varepsilon(n) = \displaystyle\sum_{d|n}\mu(d)$

除数函数 $d$ 是常数函数 $1$ 和 $1$ 的狄利克雷卷积: $d(n) = \displaystyle\sum_{d|n}1$

除数和函数 $\sigma$ 是恒等函数 $id$ 和 $1$ 的狄利克雷卷积: $\sigma(n) = \displaystyle\sum_{d|n}d$ .

欧拉函数 $\varphi$ 是恒等函数 $id$ 和莫比乌斯函数 $\mu$ 的狄利克雷卷积: $\varphi(n) = \displaystyle\sum_{d|n}d\mu(\frac{n}{d})$

gcd和函数 $P(n) = \displaystyle\sum_{i=1}^ngcd(i, n)$ 是恒等函数 $id$ 与欧拉函数 $\varphi$ 的狄利克雷卷积(所谓欧拉反演的核心).

狄利克雷卷积的性质

交换律

结合律

对加法的分配律

存在单位元, 为单位函数 $\varepsilon$

在 $f(1)\ne 0$ 时存在逆元, 称为狄利克雷逆元. 逆元满足递推公式 $\displaystyle g(n) = \frac{\varepsilon(n) - \sum_{kl = n, k \ne 1}f(k)g(l)}{f(1)}$

如上性质表明全体数论函数在加法运算和狄利克雷卷积运算下构成交换环, 称为狄利克雷环.

莫比乌斯反演#

由狄利克雷卷积可以知道 $\mu * 1 = \varepsilon$ , 即在狄利克雷环上, $\mu$ 与 $1$ 互为逆元. 我们可以利用这个性质得到: 若 $F = f * 1$ , 则 $f = F * \mu$ . 更加正式地: $\text{若}\displaystyle F(n) = \sum_{d|n}f(d), \text{则}f(n) = \sum_{d|n}\mu(d)F(\frac{n}{d})$ .

这个过程称作莫比乌斯反演. 这提醒我们: 对于某些函数 $f(n)$ , 如果我们很难直接求出它的值, 但却容易求出其倍数和或约数和 $g(n)$ 的值, 那么我们可以通过莫比乌斯反演简化运算, 从而求得 $f(n)$ 的值.