算法学习笔记：数论基础

f_K_e1207 · 2024-12-11 20:52:26 · 算法·理论

本文大部分内容参照进阶指南，其中例题参考部分题解，加上了一些自己的理解。

质数

定义

若一个整数 n>1 只能被 n 或 1 整除，则称该整数为质数，否则为合数。质数在整个自然数集合中分布较稀疏，对于一个足够大的整数 N，大约每 \ln{N} 个数中有一个质数。

质数的判定

试除法作为入门级内容不再赘述，扫描 [2,\sqrt N] 之间的整数试除即可。

质数的筛选

埃氏筛与线性筛都是求解 [2,N] 之间质数的高效算法，基本思想都是扫描 [2,N] 之间的整数，并且向上标记这些整数的倍数为合数。但是埃氏筛会重复标记合数，因此时间复杂度为 \mathcal O(N\log{\log{N}})，这里着重讲更优的线性欧拉筛。

欧拉筛是通过确定一个合数的唯一分解方式，避免合数被重复标记，从而达到线性复杂度。具体实现方法是先把 [2,n] 之内的所有数都标记为质数，然后从 [2,n] 枚举 i，如果 i 没有被之前的数标记为合数，则 i 是质数，可以用来更新后面的合数。枚举已经筛出来的质数 p_j(1\le j\le cnt)，标记 i\times p_j 为合数，如果 i 是 p_j 的倍数时退出循环。

过程比较简单，因此看起来比较莫名其妙，所以在这里给出证明。首先证明其正确性。假设合数 a 的最小质因数为 p，则设 a=p\times b，显然 b<a，因为 p 是 a 的最小质因数，所以 b 的最小质因数必然不小于 p。在整个算法过程中，b 先被 i 枚举到，然后在内层循环中找到 p，a 就被 p\times b 标记为合数了，即使 p 也是 b 的因数，也会在标记后再退出循环。接下来证明其复杂度为线性，即每个合数只被标记一次，运用反证法。对于上述假设的 a=p\times b，如果存在 a=p'c 也将 a 标记，则若 c>b，说明 p'<p， p 是最小质因数的假设矛盾；若 c<b，说明 p'>p，则 p 是 c 的质因数，且显然 p\times c<a，根据算法流程，内层循环在还没有枚举到 c 的时候就会退出循环。

贴个代码：

void euler()
{
    for (int i=2;i<=n;i++)  
        isprime[i]=1;
    for (int i=2;i<=n;i++)
    {
        if (isprime[i]) prime[++cnt]=i;
        for (int j=1;j<=cnt&&i*prime[j]<=n;j++)
        {
            isprime[i*prime[j]]=0;
            if (i%prime[j]==0) break;//维持线性复杂度的关键 
        }
    }
}

质因数分解

算数基本定理

任何一个大于一的正整数都能唯一分解为有限个质数的乘积，即：

其中 c_i 都是整数，p_i 都是质数，且满足 p_1<p_2<\cdots<p_m。由于是基本定理，所以不给出证明。感性理解，如果 N 的一个因数是合数，就可以把这个因数分解为其因数的乘积的形式，如果因数的因数还是合数，还可以再分解。通过这种类似于递归的分解，最终会得到一个全部为质数的整数分解形式。

结合质数判定的试除法和质数筛选的埃氏筛法，可以通过扫描 [2,\lceil \sqrt N \rceil] 的每一个数 d，若 d 能整除 N，则从 N 中除去所有的因数 d，同时累计除去 d 的个数，这个思路和其实现还是比较显然的。

贴个代码：

void divide(int n)
{
    m=0;
    for (int i=2;i*i<=n;i++)
    {
        if (n%i==0)
        {
            p[++m]=i;
            c[m]=0;
        }
        while (n%i==0)
        {
            n/=i;
            c[m]++;
        }
    }
    if (n>1)//特判，如果最后剩下的n还是质数，则要再进行一次分解 
    {
        p[++m]=n;
        c[m]++;
    }
}

约数

定义

设 d,n 为给定整数，那么一定存在唯一的一对整数 q,r，满足 n=qd+r,\ 0\le r<|a|，若此时 r=0 ，即 d 能整除 n，则称 d 是 n 的约数，记为 d\mid n。

此处需要分清因数与约数的区别，因数是在数的乘积关系下定义的，不一定是整数；约数是对于两个自然数的整除关系而言的，只能是自然数。

算数基本定理的推论

在算数基本定理中，若正整数满足上文中的条件，则 N 的正约数集合可以写作：

其中 0\le b_i\le c_i 。