普及数论题

几何微粒子 · 2023-03-22 20:31:27 · 个人记录

这次补的是之前的笔记。

含有算法介绍

Chapter I 除法

大家都知道小学除法罢。除非你幼儿园大班就考CSP提高

小学除法长这样：n \div p =k \dots r

但是OI常用的带余除法，也就是欧几里得除法，长这样： n=p\times k+r

该除法具有：

• 存在性（原始有意义的情况下势必存在解）

• 唯一性（只有一个解）

给定整数 n（被除数）和非零整数 p （除数），存在唯一的整数 k （商） 与 r（余数），其中 0\le r < |p|

其中k=\left\lfloor\dfrac{n}{p}\right\rfloor , r = n \mod p

例如：-5/3向下取整=-2，向零取整=-1

那%是啥意思？a%b等价于a膜拜b？

c++中的%为取模运算

在c++中，%运算符的运行规则为取余

两数取余，结果符号看被除数

e.g.

5%3=2
5%-3=2
-5%3=-2
-5%-3=-2

所以在取模的时候不需要考虑除数的正负情况。但请注意防爆和题目限制！

1. 有些时候题目的玄学限制可能会导致%一个负数的答案仍然是错的。

2. 小心类型溢出

3. 当式子里出现减法运算或各个参数/变量中有负数的时候，参考第一条，万分小心，同时注意这个参数/变量的正负是否会影响其他的因素。

• 而对于 \gcd （手打辗转相除法）而言，由于内部含有取模运算符%，其大致情况是这样的：

int gcd(int a,int b){
    if(b==0){
        return a;
    }
    else{
        return gcd(b,a%b);
    }
}

gcd(12,-8)=4
gcd(-12,8)=-4
gcd(-12,-8)=-4
gcd(8,-12)=-4
gcd(-8,12)=4
gcd(-8,-12)=-4

你猜对了吗？真聪明！清华北大不是梦

Chapter II 整数唯一分解定理

• 算术基本定理

任意 \ge 1 的自然数 n 都可以唯一地分解为有限个质数的乘积。

其中 p_1 < p_2 < \dots < p_k ，r_i 为正整数

上述式子也被称为n的标准分解式

这个定理可以把对自然数的研究转换成对质数的研究，且不需要分类讨论——因为是唯一的。

gcd和lcm在整数唯一分解定理中的应用

\gcd(a,b) = p_1^{\min(r_{a_1},r_{b_1})} \times p_2^{\min(r_{a_2},r_{b_2})} \times \dots \times p_k^{\min(r_{a_k},r_{b_k})}

lcm (a,b) = p_1^{\max(r_{a_1},r_{b_1})} \times p_2^{\max(r_{a_2},r_{b_2})} \times \dots \times p_k^{\max(r_{a_k},r_{b_k})}

公式太大，只能开大标题了

• 整数唯一分解定理和欧拉函数 \varphi

欧拉函数的定义详见这里的Chapter IV

• 整数唯一分解定理和约数个数 d

d_n = (r_1+1)\times (r_2+1)\times \dots (r_k+1)

• 整数唯一分解定理和约束和 \sigma

\sigma_n = (1 + p_1 + p_1^2 + \times + p_1^{r_1}) \times (1 + p_2 + p_2^2 + \times + p_2^{r_2}) \times (1 + p_n + p_n^2 + \times + p_n^{r_n})

分解质因数的方法

方法1

利用性质：

流程：

• 试除 2 ~ \sqrt{n} 内的质数

时间复杂度：O(\sqrt{n})

适用范围：

• 时间限制非常宽松

• 需要简单快速的代码实现

• 像CF等的手速赛。

• 小型数据范围

优点：

• 简单方便

• 空间需求低

缺点：

• 时间需求高，多半不稳

方法2

利用性质：

• \pi(n)$ ~ $\dfrac{n}{\ln n}

流程：

• 预处理 1 ~ \sqrt{n} 内的质数（使用线性筛）

• 分解时仅仅试除质数

时间复杂度： O(\sqrt{n})/O(\dfrac{\sqrt{n}}{\log n })

适用场景：

• n \le 10^9$ ~ $10^{14}

• 时间限制比较紧，且算法1不稳的时候

优点：

• 思路比较直白

• 相对于大数据而言在时间方面提供了强有力的制裁

• 记录质数可以直接使用线性筛里用来记录质数的数组

• 大型数据范围

缺点：

• 极限数据下非常不稳

• 数据中小的情况下不能发挥时间上的制裁优势

关于线性筛法：

时间复杂度分析在这里的Chapter V

代码在这里的Chapter I

线性筛思路：

• 每个合数被他的最小质因数筛去。

• 如果一个数内部含有两个相同的质因数就可以滚蛋下一个了。

• 第二条在代码里的实现即为i % p[j] == 0，也就是( i * p[j] ) % ( p[j] * p[j] ) == 0

方法3

利用性质：

• 整数唯一分解定理

流程：

• 线性筛的时候记录每个数最小的质因数

• 分解时直接除掉最小质因数

时间复杂度：O(n)/O(\log n)

适用场景：

• n \le 10^6$ ~ $10^7

• 分解次数较多，时间限制紧，极限数据下、算法2不稳的时候。

优点：

• 耐分解，次数多不怕

• 比较稳定

• 思路比较直白（分解质因数的方法都™直白）

• 中型数据范围

缺点：

• 需要多开一个 minprime 数组来记录每个数的最小质因数

方法4

Phollard-Rho算法

• 基于玄学随机化的质因数分解算法。

• 一场胜率很大的赌博——很大的概率分解对。

• 期望时间复杂度： O(n^\frac{1}{4})

• 适用场景：n \le 10^{18}

同样随机化的素数检测算法是Miller-Rabin

• 当判定16个质数时，只有\dfrac{1}{4\times 10^6}的概率判错

找约数

问题：如何高效地找到 n 的所有约数

方法1

利用性质：

• 无

流程：

• 试除 1 ~ \sqrt n 内的整数

时间复杂度： O(\sqrt n)

适用场景：

• 其他方法写不了了

• 空间卡的逆天

• 题目的时间限制特别宽松，不值得在这个题上优化（优化约等于浪费时间的情况）

• 脑子抽抽只会暴力了

优点：

• 省事

• 空间更少

缺点：

• 时间功耗大

• 同分解质因数方法1，特别不稳定

方法2

利用性质：

• \sum\limits_{i=1}^{n} d_n = \sum\limits_{i=1}^{n}$ ~ $n\ln n

流程：

• 预处理 1 ~ n 的每个约数

时间/空间复杂度：O(n\log n)

适用场景：

• 多组询问

优点：

• 预处理，多组询问不用怕

缺点：

• 如果询问少，数据范围又大，则在绝大部分情况下是不划算的，除非这道题的条件玄学地卡得你只能用这种方法找约数。

方法3

利用性质：

• d | n \Rightarrow d = p_1^{a_1} p_2{a_2} \dots p_k^{a_k} (0 \le a_i \le r_i)

流程：

• 分解质因数

• dfs或者循环枚举指数

• 时间复杂度 O(???) + O(d_n)

适用范围：

• 较广泛

优点：

• 运用了整数唯一分解定理，高级，可以同时套一些其他的东西

缺点：

• 复杂度是个玄学问题

• 如果其他的东西不用分解质因数，除非像方法2说的那样给玄学卡死了，用这个方法似乎血亏

找约数

一些算法的复杂度与 d_n 相关，分析复杂度的时候需要分析：

上述式子取得最大值的最小 x 被称为反素数

Chapter III 线性筛总结

通过线性筛预处理数论函数，需要处理两个基本问题

• 计算在质数处的取值 f_p

• 由 f_i 递推得到 f_{i\times p}

能正确求出数论函数的条件：每种不同的质因子贡献独立

复杂度线性的条件：添加一个质因子时，函数值能够快速递推

• 质数处取值 f_p 要求 O(\log n) 内求出（素数定理）

• 由 f_i 递推得到 f_{i\times p} 的复杂度必须为 O(1)