机试小课堂丨C++ 数论，不仅漂亮，其实也有大用处！
【声明：本文为原创文章,未经同意,严禁转载和抄袭,违者将追究其法律责任】
/ 写在前面的话 /
苏世机试小课堂，考研机试不再慌！
公主号：苏世学社考研 苏世计算机考研
数论一度被认为是漂亮的但没什么大用处的纯数学学科。今天，有关数论的算法被广泛使用，部分是因为基于大素数的密码系统的发明。这些系统的可行性在于我们容易求出大素数，而系统的安全性在于大素数的积难以分解。本文介绍一些初等数论和相关算法，它们是一些应用的基础。
数论常用内容介绍
1
同模余定理
1.1 概念
同余，顾名思义，就是许多数被一个数d除，有相同的余数。d在数学上的称谓为模。比如a=7,b=2,d=5，那么我们说a和b是模d同余的，因为他们都有相同的余数1。
可以看出，当x<d的时候，所有的x都对d同商，对于同余有三种说法是等价的，分别是：
①a和b是模d同余的；
②存在某个整数n,使得a = b + nd；
③d整除(a - b)。
1.2 常用操作
(a+b)%d=(a%d+b%d)%d；
(a-b)%d=(a%d-b%d)%d；
(a*b)%d=(a%d*b%d)%d。
1.3 栈的应用——括号匹配
题目描述
S(n)=n^5，求S(n)除以3的余数。
输入描述
每行输入一个整数n(0 < n < 1000000)，处理到文件结束。
输出描述
输出S(n)%3的结果并换行。
样例输入
1
2
样例输出
1
2
思路分析
n^5超过了long long的范围，题目要求对结果%3，可运用同余模定理。
S(n)%3=(n*n*n*n*n)%3=((n%3)*(n%3)*(n%3)*(n%3)*(n%3))%3
代码实现
运行结果
2
最大公约数（GCD）
2.1 概念
最大公约数，也称最大公约数、最大公因子，指两个或多个整数共有约数最大的一个。a,b的最大公约数记为(a,b)，a,b,c的最大公约数记为(a,b,c)，多个整数的最大公约数也是类似的记号。
2.2 解题方法
（1）穷举法一：
用一个临时变量t保存其中一个数，然后看两个数是否都能被t整除，能就输出，不能就减1，直到减到1，1是任意两个正整数的公约数。
（2）穷举法二：
求出两个数的所有公因子，累乘得到最大公约数。
（3）辗转相除法：
两个数辗转相除直到余数为0。
（4）辗转相减法：
3
最小公倍数
3.1 概念
两个或多个整数公有的倍数叫做它们的公倍数，除了0以外最小的一个公倍数叫做这几个整数的最小公倍数。整数a,b的最小公倍数记为[a,b]，整数a,b,c的最小公倍数记为[a,b,c]，多个整数的最小公倍数是同样的记号。
3.2 代码思路和实现
①设置一个临时变量t初始值等于其中一个数，开始遍历到两个数的乘积为止，遇到一个数能同时被a,b整除就跳出循环打印输出。
这里当a和b的乘积太大溢出了怎么办呢？
②利用一个公式：两个数的乘积等于它们的最大公约数乘最小公倍数。所以求最小公倍数就用两数乘积除以它们的最大公约数。
这里以辗转相减法求最大公约数为例：
4
素数判定
4.1 概念
素数，又叫质数，有无限多个。定义为在大于1的自然数中，除了1和它本身外不再有其他因数，这样的数叫做质数。
比如13就是素数，它不能被2~12的任意一个整数整除。
4.2 判断方法及代码实现
简单粗暴的方法就是遍历从2到这个数n-1，时间复杂度为O(n)，想想还有没有可以减少遍历次数的上限值呢？
如果一个数能被2整除，还需要试4,6,8....吗？
如果一个数能被3整除，还需要试9,15,21....吗？
所以，一个数如果有因子那么在它的平方根数以内就应该有，否则就没有。
参考代码如下：
5
素数筛选
5.1 概念
有时候我们可能会遇到打印一个整数以内的所有素数或者求所有素数个数的问题，这个时候我们再一个一个去判断是不是素数时间成本就太高了，所以我们需要提前打表筛选。
5.2 典型题目及代码思路和实现
给定一个数字n，求出小于等于n的素数的个数，假设n<=1e6。
（1）埃氏筛选法
遍历2~N的所有数，如果是素数，就把它的倍数全部标记为合数，最后根据题目条件输出即可。
（2）欧拉筛选法
原理是保证2~N内的每一个合数都能被唯一分解成它的最小质因数与除自己外最大的因数相乘的形式。
假设所有1e6范围内的数都是素数，枚举2~N中的每一个数作为筛法中的“除自己外的最大因数”，如果没有被标记为合数，就放进素数表，再将这个最大因数与素数表中已经找到的素数作为最小质因数相乘，将得到的数标记为合数，最后根据题目条件相应输出即可。
6
分解素因数
6.1 概念
每个合数都可以写成几个质数相乘的形式。其中每个质数都是这个合数的因数，叫做这个合数的分解质因数。分解质因数只针对合数。分解质因数的算式叫短除法，求一个数分解质因数，要从最小的质数除起，一直除到结果为质数为止。
6.2 代码实现
7
二分快速幂
求a的b次方，自定义pow库函数：
pow(a,b)是数学头文件cmath里面有的函数，但是返回值是double，数据有精度误差。
但是当数据量大时会超时，使用自定义的pow也要超时，这时必须二分快速幂。
（1）递归写法：
（2）循环写法：
苏世学社旗下品牌，专注于计算机考研
计算机考研一手资讯，原创高质量干货
深度的学习分享丨咨询前辈丨个性化指导
