数数论

约数

字数统计: 1.1k字   |   阅读时长: 4分

摘要: 本文介绍约数的定理

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，本文详细研究约数以及相关的定理。主要内容如下：

  • 约数的定义
  • 算术基本定理
  • 算术基本定理的推论
  • 求正约数集合
    • N : 试除法
    • 1~N : 倍数法
  • 最大公约数
    • 更相减损术
    • 欧几里得算法(辗转相除法)
  • 互质和欧拉函数
  • 积性函数

约数的定义

若整数 n 除以 d 的余数为 0，即 d 整除 n，则 d 为 n 的约数，n 是 d 的倍数，记为 $d | n$。

算术基本定理

任何一个大于 1 的自然数 N，如果 N 不为质数，那么 N 可以唯一分解成有限个质数的乘积 $N = P_{1}^{c_{1}}P_{2}^{c_{2}}…P_{k}^{c_{k}}$，称该式为 N 的标准分解式。

相关题目 1390. 四因数，题解参考 力扣1390-四因数。

算术基本定理的推论

按照算术基本定理：$N = P_{1}^{c_{1}}P_{2}^{c_{2}}…P_{k}^{c_{k}}$，其中 $c_{i} \in N^{*}$, $p_{i}$ 为质数且 $p_{1} < p_{2} < … < p_{k}$。

  • N 的正约数集合：$\{p_{1}^{b_{1}}p_{2}^{b_{2}}…p_{k}^{b_{k}}\}$，其中 $0 \leq b_{i} \leq c_{i}$
  • N 的正约数个数：$\prod\limits_{i=1}\limits^{k}(c_{i} + 1)$
  • N 的正约数和：$\prod\limits_{i=1}\limits^{k}(\sum\limits_{j=0}\limits^{c_{i}}(p_{i})^{j})$

求正约数集合

N : 试除法

扫描 $d = 1..\sqrt{N}$，尝试 d 能否整除 N，若能整除，在结果中记录 $d$ 和 $N/d$，时间复杂度 $O(\sqrt{N})$

推论：N 的约数个数上界为 $2\sqrt{N}$

1~N : 倍数法

对于每个数 d，1 ~ N (注意这里不是 $1~\sqrt{N}$ 了)中以 d 为约数的数就是 d 的倍数：$d, 2d, 3d, …, \lfloor N/d \rfloor * d$

1
2
3
4
5
6
7
vector<vector<int>> factor(N + 1)
// factor[i] := 数字 i 的正约数集合
for(int i = 1; i <= N; ++i)
    for(int j = 1; j <= n / i; ++j)
    {
        factor[i * j].push_back(i)
    }

时间复杂度 $O(N+N/2+N/3+…+N/N) = O(N\log N)$

推论：1～N 每个数的约数个数的总和大约 $O(N\log N)$

最大公约数

更相减损术

1
2
gcd(a, b) = gcd(b, b - a) = gcd(a, a - b)    a>=b
gcd(2a, 2b) = 2gcd(a, b)
1
2
3
4
5
6
7
8
ll gcd(ll a, ll b)
{
    if(a < b)
        return gcd(b, a);
    if(b == 0)
        return a;
    return gcd(a, a - b);
}

欧几里得算法(辗转相除法)

1
2
3
4
5
6
ll gcd(ll a,ll b)
{
    if(b == 0)
        return a;
    return gcd(b, a % b);
}

细节参考 【C++17】最大公约数。

因为高精度除法(取模)不容易实现，当需要做高精度运算时，可以考虑用更相减损术替换欧几里得算法。

互质和欧拉函数

互质的定义

$\forall a, b \in \mathbb{N}$，若 $gcd(a, b) = 1$，则称 a, b 互质。

a,b,c 互质: $gcd(a,b,c) = 1$

a,b,c 两两互质: $gcd(a,b) = gcd(b,c) = gcd(a,c) = 1$

欧拉函数

1~N 中与 N 互质的数的个数为欧拉函数，记为 $\phi(N)$

在算术基本定理中：$N = P_{1}^{a_{1}}P_{2}^{a_{2}}…P_{k}^{a_{k}}$

证明要用到容斥原理，参考 组合数学4-容斥原理,鸽巢原理。

欧拉函数性质：

  1. $\forall n > 1, [1..n] 中与 n 互质的数的和为 n * \phi(n)/2$
  2. 若 a,b 互质，则 $\phi(ab) = \phi(a)\phi(b)$

积性函数

当 $a, b$ 互质时，有 $f(ab) = f(a)f(b)$，那么 f 为积性函数。

积性函数性质：

若 f 为积性函数，且在算术基本定理中 $n=\prod\limits_{i=1}\limits^{k}p_{i}^{a_{i}}$，则 $f(n) = \prod\limits_{i=1}\limits^{k}f(p_{i}^{a_{i}})$

欧拉函数进一步性质：

  1. p 为质数，若 $p|n$ ，且 $p^{2}|n$ 则 $\phi(n) = \phi(n/p)*p$
  2. p 为质数，若 $p|n$ ，且 $p^{2} \nmid n$ 则 $\phi(n) = \phi(n/p)*(p-1)$
  3. $\sum\limits_{d|n}\phi(d)=n$

用筛法可以求解积性函数。参考 素数筛。

Share