Hellc

数论基础学习笔记（一）

数论，古老，纯粹，优美，数学王国的皇后。 —— 题记

在OI中，数论常以千变万化的面貌出现，对数学思维和能力要求较高。然而万变不离其宗，再难的问题都是由简单的问题扩展而来的。

所以总结了本文，记录自己学习到的数论中那一点点皮毛，那一些最* 基本的东西。

【基本概念】

带余除法
取模
同余
因子
互质

等等，过于基础，不再具体介绍。

【模意义下的运算】

常见的加减乘在模意义下都是封闭的，即： $$ (a + b) % P = (a % P + b % P) % P $$ $$ (a - b) % P = (a % P - b % P) % P $$ $$ a * b % P = (a % P) * (b % P) % P $$

注意这里的%是取模而不是取余。

也就是说如果只涉及加减乘，最后结果取模，那么计算时可以随时取模，结果不变。

至于除法，并不满足这个性质，接下来的逆元部分会讨论。

注意，代码的世界并不像数学公式一样美好。很多时候，题目中给出的模数是在int范围内的，因此最后的结果取模后在int范围内。然而如果你~~naive地~~直接两个将int直接相乘，中间结果可能会产生溢出的现象。

这时我们要将其转化为long long的临时类型，很多地方都会用到，为保持代码整洁，写成函数。

当然变量本身直接用long long也无不可。

typedef long long int64; // 这样写只是个习惯

inline int mulMod(int a, int b){
    return (int64)(a % MOD) * (b % MOD) % MOD;
}

如果确定传入的a b都是取过模的，相乘前可以不取模以加快速度。

要是连long long也不够用怎么办，就只能手写~~（讨厌的）~~高精度了吗？幸运的是，还是有着简单解决方案的，这一点将在下边【快速乘】部分讨论。

【算数基本定理】

算数基本定理，又称正整数唯一分解定理，内容为：

算数基本定理任何一个大于1的自然数$N$,如果$N$不为质数，那么$N$可以唯一分解成有限个质数的乘积，记作$N=P_1^{a_1}P_2^{a_2}P_3^{a_3}......P_n^{a_n}$，这里$P_1<P_2<P_3......<P_n$且均为质数，其中指数$a_i$是正整数

这样的分解式称作$N$的标准分解式，也可记作: $$N = \prod p_i^{a_i} $$

算术基本定理是初等数论中一个基本的定理，也是许多其他定理的逻辑支撑点和出发点。

【最大公约数】

两数$x, y$的最大公约数(Greatest Common Divisor, GCD)，指两数共有约数中最大的一个，记作$gcd(x, y)$。

常见的求最大公约数的方法有更相减损术与辗转相除法。

【辗转相除法】

辗转相除法，又称欧几里得算法，用于求解两数的最大公约数，其正确性基于恒等式：$gcd(a,b) = gcd(b, a % b )$，该恒等式与边界条件$gcd(a, 0) = a$共同构成了该算法。

【代码】->

int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}

时间复杂度$O(logN)$，其中$N = max(a, b)$，值得一提的是，让该算法递归层数最深的是斐波那契数列中的相邻项。

【更相减损术】

更相减损术，同样用于求解两数的最大公约数，但应用相对较少。其正确性基于恒等式：$gcd(a, b) = gcd(a - b,b)$。

多次更相减损等价于一次辗转相除，与辗转相除法的本质相同。

更相减损术稍作优化，便可以得到复杂度也有对数阶保证的Stein算法(好吧其实很少叫这名字)。

简单来说：若当前两数均为偶数，则令其均除以二，并将结果乘二。若有一个为奇数，则将偶数除以二。若均为奇数，则相减后除以二。

一般情况下我们使用辗转相除法较多，但改进后的更相减损术，在某些场景下也有着不错的表现。

一个例子是高精度整数的最大公约数。

如果采用辗转相除法，意味着我们要编写高精度取模，不仅难写而且效率十分低下。

如果采用优化过的更相减损术，则效率更高，编程复杂度也更低。

【代码】 ->

省略了高精度代码。

BigInt bigGcd(BigInt x, BigInt y){
    if(x < y) std::swap(x, y);

    if(y.isZero()) return x;

    bool a = x.isEven(), b = y.isEven();

    if(a && b) return 2 * bigGcd(x / 2, y / 2);
    else if(a) return bigGcd(x / 2, y);
    else if(b) return bigGcd(x, y / 2);
    else return bigGcd((x - y) / 2, y);
}

【最小公倍数】

我们也可以借助最大公约数来求最小公倍数。

对于数$a, b$，有$ab = gcd(a, b)lcm(a, b)$。这个结论可以简单地由唯一分解定理得到。

简要证明，设： $$ x = \prod P_i^{a_i}$$ $$ y = \prod P_I^{b_i} $$

那么： $$ gcd(x, y) = \prod P_i^{min(a_i, b_i)} $$ $$ lcm(x, y) = \prod P_i^{max(a_i, b_i)} $$

乘起来： $$ xy = \prod P_i^{ a_i + b_i} $$ $$ gcd(x, y)lcm(x,y) = \prod P_i^{min(a_i,b_i) + max(a_i, b_i)} $$ 而这一点是显然的： $$ a_i + b_i = min(a_i, b_i) + max(a_i, b_i) $$

证毕。

【最小公倍数代码】 ->

inline int lcm(int a, int b){
    return a / gcd(a, b) * b; // 先除后乘防炸
}

【快速幂】

计算$a^k \pmod{MOD}$

首先我们知道，计算过程中可以随时取模。

显然我们有着复杂度为$O(k)$的朴素算法，但有时候这样的复杂度无法满足要求。

考虑二进制的思想，由二进制计数原理可知，指数$k$必然可以为若干个2的幂之和。

那么$a^k$必然可以表示为若干个a的 2的幂次方的积，有点绕口，看个例子。

所以我们只需要计算 $a^0, a^1, a^2, a^4, a^8 ...$，而后一项是可以由前一项平方得到。

这样就将复杂度降到了 $O(logk)$。

给个栗子：比如说$a^{11}$，$11$的二进制表示为$(1011)_2$。那么 $$ a^{11} = a^{2^0 + 2^1 + 2^3} $$ 即 $$ a^{11} = a^{2^0} * a^{2^1} * a^{2^3} $$

代码写法如下：

【快速幂迭代代码】 ->

inline int fastPowMod(int x, int k){
    int ans = 1;
    for(; k; x = mulMod(x, x), k >>= 1) if(k & 1) ans = mulMod(ans, x);
    return ans;
}

快速幂还有一种递归写法，更加易于理解。

如果指数为奇数，就减一，然后结果乘上x。如果指数为偶数，就除二，然后结果平方。

【快速幂递归代码】 ->

int fastPowMod(int x, int k){
    if(k == 1) return x;
    else if(k & 1) return mulMod(fastPowMod(x, k - 1), x);
    else return fastPowMod(mulMod(x, x), k >> 1);
}

这种写法的优势在于易于理解，而且易于扩展。底数可以为任意类型 —— 只要它支持乘法操作就够了。

【Eratosthenes 筛法】

埃拉托斯特尼筛选，下简称埃式筛法。

用埃式筛法求素数的基本思路是：

首先生成1到n的序列，暂且认为每个数都是素数。 1不是素数，首先把它筛掉。在剩下的数中选择最小的数，该数必然是素数，然后筛掉它的倍数。为什么这个最小的数必然是素数呢，因为它已经被小于它的数字筛过一遍了。依次类推，直到筛完为止。

给出代码：

bool isPrime[MAXN + 1];
std::vector<int> primes;

inline void initPrime(int n) {
    std::fill(isPrime + 1, isPrime + n + 1, true);
    isPrime[1] = false;

    int m = (int)sqrt(n) + 1;
    for(int i = 2; i <= m; i++) if(isPrime[i]){
        for(int j = i * i; j <= n; j += i) isPrime[j] = false;
    }

    for(int i = 2; i <= n; i++) if(isPrime[i]) primes.push_back(i);
}

一些优化。首先，外层质数枚举到 $\sqrt n$ 即可，因为一个合数 $n$ 必然有至少有一个质因子 $k$ ，使得 $k ≤ \sqrt n$。其次，内层循环可以从 $i^2$ 开始，因为所有小于 $i^2$ 的 $i$ 的倍数 $x$ ，已经在之前被 $x/i$筛掉了。

时间复杂度：$O(nloglogn)$，不是线性，但实际表现还是不错的。

真正的线性筛回来和数论函数放到一起写吧。

筛法还可以顺便处理处 $[1, n]$ 中每个数的最小质因子，因为每次一个数必然是被其最小质因子筛掉的。

设作 $minPrimeFact$ 数组，这玩意儿有什么用呢？且看下文。

【分解质因数】

如何枚举一个数的所有质因子？

暴力一点的 $O(\sqrt n)$ 做法。在 $[2, \sqrt n]$ 中从小到大枚举因子，每次找到后将这个因子"除干净"。这样即可保证每次枚举到的因子都是质因子。为什么这样做是对的呢？类似筛法，每次将一个因子"除干净"相当于筛掉了该因子的倍数。

std::vector<int> facts;

int m = (int)sqrt(n);
for(int i = 2; i <= m; i++) if(n % i == 0){
    primeFacts.push_back(i);
    while(n % i == 0) n /= i; // 事实上在这一层循环处理掉了质因子i的幂。
}
if(n != 1) primeFacts.push_back(n);

如果我们已经用筛法预处理出了每个数的最小质因子，那么我们可以在 $O(质因子个数)$ ≈ $O(logn)$ 的时间内完成分解质因数。

std::vector<int> primeFacts;

while(n != 1){
    int i = minPrimeFact[n];
    primeFacts.push_back(i);
    while(n % i == 0) n /= i;
}

有点长，断开好惹QwQ 。

传送门 -> 数论基础学习笔记（二）