数学

发表于 更新于 分类于 Waline：
摘要：和数学相关的一些东西

一些学习数学的笔记，学了什么就写点什么，所以内容会特别杂（

欧拉函数

定义

欧拉函数 $\varphi(n)$，表示小于等于 $n$ ，且与 $n$ 互质的数字个数。

性质

  • $n$ 为质数时，$\varphi(n)=n-1$。
  • 是积性函数，即若 $a,b$ 互质，则有 $\varphi(ab)=\varphi(a)\varphi(b)$。其中比较特殊的是：当 $n$ 是奇数时，$\varphi(n)=\varphi(2n)$。
  • $n=\sum_{d|n}\varphi(d)$。
  • 设分解质因数后 $n=\prod_{i=1}^sp_i^{k_i}$，则 $\varphi(n)=n\prod_{i=1}^s\frac{p_i-1}{p_i}$。

求值

单个欧拉函数的计算

根据上面的第四条性质，可以枚举 $n$ 的质因数进行计算，时间复杂度 $O(\sqrt n)$。

1
2
3
4
5
6
7
8
9
10
11
int phi(int x)
{
    int res = x;
    for(int i = 2; i <= sqrt(x); i++) if(x % i == 0)
    {
        res /= i, res *= (i - 1);
        while(x % i == 0) x /= i;
    }
    if(x != 1) res /= x, res *= (x - 1);
    return res;
}

预处理前 N 个欧拉函数的值

在线性筛的过程中，设 $n$ 的最小质因子为 $p_1$，设 $q=\frac{n}{p_1}$，则 $n$ 一定是通过 $p_1\times q$ 筛掉的。我们假设已经求出了 $\varphi(q)$ 的值，目标是推出 $\varphi(n)$。在这个过程中我们分两种情况：

1. $q$ 是 $p_1$ 的倍数

注意到此时 $n$ 和 $q$ 的质因子是相同的，那么：

即可推出 $\varphi(n)$ 的值。

2. $q$ 不是 $p_1$ 的倍数

此时 $q$ 与 $p_1$ 一定互质。欧拉函数是积性函数，可以用这条性质来推：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool np[N]; // not prime
int phi[N];
void init()
{
    int n = 1000000;
    phi[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        if(!np[i])
            prm.push_back(i), phi[i] = i - 1; // i 是质数，则 φ(i)=i-1
        for(auto j : prm)
        {
            if(i * j > n) break;
            np[i * j] = 1;
            if(i % j == 0)
            {
                phi[i * j] = j * phi[i]; // 第一种情况
                break;
            }
            phi[i * j] = phi[i] * (j - 1); // 第二种情况
        }
    }
}

应用

欧拉函数可以解决对一些 $\gcd$ 进行求和的问题。

利用性质：

可以得出：

欧拉定理

若 $\gcd(a,m)=1$，则 $a^{\varphi(m)} \equiv 1 \pmod{m}$。

莫比乌斯反演

莫比乌斯函数

$\mu$ 是莫比乌斯函数：

性质

  • 莫比乌斯函数是积性函数。
  • $\sum_{d|n}\mu(d)=[n=1]$。

反演结论：$[\gcd(a,b)=1]=\sum_{d|\gcd(a,b)}\mu(d)$。

莫比乌斯变换

设 $f(n),g(n)$ 是两个数论函数。若有 $f(n)=\sum_{d|n}g(d)$，则有：

  • 形式一：$g(n)=\sum_{d|n}\mu(d)f(\frac{n}{d})$
  • 形式二：$g(n)=\sum_{d|n}\mu(\frac{n}{d})f(d)$

容易看出两种形式本质上是相同的。