数学

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

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

欧拉函数

定义

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

性质

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

求值

单个欧拉函数的计算

根据上面的第四条性质，可以枚举 nn 的质因数进行计算，时间复杂度 O(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 个欧拉函数的值

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

1. qq 是 p1p_1 的倍数

注意到此时 nn 和 qq 的质因子是相同的，那么：

φ(q)=q∏i=1spi−1pi\varphi(q)=q\prod_{i=1}^s\frac{p_i-1}{p_i}

φ(n)=n∏i=1spi−1pi=p1×q∏i=1spi−1pi=p1×φ(q)\varphi(n)=n\prod_{i=1}^s\frac{p_i-1}{p_i}=p_1\times q\prod_{i=1}^s\frac{p_i-1}{p_i}=p_1\times \varphi(q)

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

2. qq 不是 p1p_1 的倍数

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

φ(n)=φ(p1×q)=φ(p1)×φ(q)=(p1−1)×φ(q)\varphi(n)=\varphi(p_1\times q)=\varphi(p_1)\times\varphi(q)=(p_1-1)\times\varphi(q) 

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 进行求和的问题。

利用性质：

n=∑d∣nφ(d)n=\sum_{d|n}\varphi(d)

可以得出：

gcd⁡(a,b)=∑d∣gcd⁡(a,b)φ(d)=∑d∣a,d∣bφ(d)\gcd(a,b)=\sum_{d|\gcd(a,b)}\varphi(d)=\sum_{d|a,d|b}\varphi(d)

∑i=1ngcd⁡(i,n)=∑i=1n∑d∣i,d∣nφ(d)=∑d∣n∑1≤i≤n,d∣iφ(d)=∑d∣n⌊nd⌋φ(d)\sum_{i=1}^n \gcd(i,n)=\sum_{i=1}^n\sum_{d|i,d|n}\varphi(d)=\sum_{d|n}\sum_{1\le i\le n,d|i}\varphi(d)=\sum_{d|n}\lfloor\frac{n}{d}\rfloor\varphi(d)

∑i=1n∑j=1ngcd⁡(i,j)=∑i=1n∑j=1n∑d∣i,d∣jφ(d)=∑d∑1≤i≤n,d∣i ∑1≤j≤n,d∣jφ(d)=∑d⌊nd⌋2φ(d)\sum_{i=1}^n \sum_{j=1}^n \gcd(i,j)=\sum_{i=1}^n \sum_{j=1}^n\sum_{d|i,d|j}\varphi(d)=\sum_d\sum_{1\le i \le n,d|i}~\sum_{1\le j \le n,d|j} \varphi(d)=\sum_d\lfloor\frac{n}{d}\rfloor^2\varphi(d)

欧拉定理

若 gcd⁡(a,m)=1\gcd(a,m)=1，则 aφ(m)≡1(modm)a^{\varphi(m)} \equiv 1 \pmod{m}。

莫比乌斯反演

莫比乌斯函数

μ\mu 是莫比乌斯函数：

μ(n)={1n=10n有平方因子(−1)k其它情况，设k为n本质不同的质因子个数\mu(n)=\begin{cases} 1 & n=1 \\ 0 & n有平方因子 \\ (-1)^k & 其它情况，设k为n本质不同的质因子个数 \\ \end{cases}

性质

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

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

莫比乌斯变换

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

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

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