《算法竞赛中的初等数论》（五）正文 0x50筛法（ACM _ OI _ MO）数论书(1)

简介：
《算法竞赛中的初等数论》是一部专为ACM（国际大学生程序设计竞赛）、OI（信息学奥林匹克）和MO（数学奥林匹克）等学科竞赛需求而编写的数论教材。该书系统地阐述了数论领域的基础知识，并特别强调了针对数论问题的快速解决方法。本文将深入探讨其中包含的0x50筛法和线性筛法，并详细说明它们在计算欧拉函数、莫比乌斯函数以及约数个数方面的具体应用。 该筛选方法被广泛应用于计算特定区间内全部素数值的高效技术。在此筛选机制中，关键策略是使每一个合成数仅被其最小的素因数进行一次过滤，从而实现算法的时间复杂度呈O(n log log n)的线性增长。实现该筛选方法时，一般会使用一个标记数组vis来跟踪当前已被过滤的数值，并配合一个素数列表primes以收集和保存最终识别出的所有素数。线性筛法是一种更为普遍的技巧，不仅局限于质数筛选，还可广泛应用于积性函数计算方面。积性函数即为那些其取值仅由输入数值质因数分解决定的数学函数。举个例子，欧拉函数φ(n)就是一个典型的积性函数，它表示小于或等于n且与n互质的正整数数量。在线性筛法中，每个合成数i被其最小的素因数过滤出去时，这个过程也会自然地记录下关于它的基本素因数信息。因此，在计算欧拉函数的过程中，这一特性使得求解变得较为简便。下面我们提供一个具体的实现方案：```cpp void get_euler(int n) { phi[1] = 1; for(int i = 2; i <= n; ++i) { if(!vis[i]) { primes[++cnt] = i; phi[i] = i - 1; } for(int j = 1; j <= cnt && i * primes[j] <= n; ++j) { vis[i * primes[j]] = true; if(i % primes[j] == 0) { phi[i * primes[j]] = phi[i] * primes[j]; break; } phi[i * primes[j]] = phi[i] * (primes[j] - 1); } } } ```同样地，在计算莫比乌斯函数μ(n)时，可以采用与前面同样的思路。作为解析数论中的一个关键函数，莫比乌斯函数的定义基于质因子的数量：如果n具有偶数个不同的质因子，则其值为-1；若有奇数个不同的质因子，则其值为+1；特别地，当n等于1或者存在重复质因子时，莫比乌斯函数μ(n)的值则为0。同样有效的是线性筛法，在分析每个合数的质因数分解情况后，可以确定莫比乌斯函数的具体数值。另外，线性筛法还可以用于计算约数个数函数d(n)，它表示n的正因子数目。具体而言，我们可以维护一个sum数组，将每个数对应的莫比乌斯函数值累加起来，从而得到d(n)的前缀和序列。这样可以快速查询任意给定整数n的约数个数。以下是用于计算d(n)的线性筛法代码片段：```cpp void get_mu(int n) { cnt = 0, mu[1] = 1; for(int i = 2; i <= n; ++i) { if(!vis[i]){ primes[++cnt] = i; mu[i] = -1; } for(int j = 1; j <= cnt && i * primes[j] <= n; ++j) { vis[primes[j] * i] = 1; if(i % primes[j] == 0) break; mu[i * primes[j]] -= mu[i]; } } for(int i = 1; i <= n; ++i) sum[i] += sum[i - 1] + mu[i]; } ```在算法竞赛领域中，0x50筛法与线性筛法被视为解决数论问题的重要工具。这些方法可应用于查找素数、计算欧拉函数以及莫比乌斯函数，同时也能用来确定约数的个数。深入掌握这些方法后，在比赛中能够迅速解决相关问题，并显著提升解题速度。