1.最大公约数
一、辗转相除法（欧几里得算法）
（1）简介
以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数
（2）本质
a/b =k（余r） (a,b)的公约数与(b,r)的公约数相同，把求(a,b)的公约数转化为求(b,r)的公约数
（3）例题
例1：求 12 和 20 的最大公约数
20 ÷ 12= 1（余 8）
12 ÷ 8= 1（余 4）
8 ÷ 4= 2（余 0）
至此，最大公约数为4
以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 12 和 20 的最大公约数 4。
例2：求 1997 和 615 的最大公约数
1997 ÷ 615 = 3 (余 152)
615 ÷ 152 = 4(余7)
152 ÷ 7 = 21(余5)
7 ÷ 5 = 1 (余2)
5 ÷ 2 = 2 (余1)
2 ÷ 1 = 2 (余0)
至此，最大公约数为1
（4）结论
以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。
（5）证明过程
证明：对于a / b = k (余 r )
a可以表示成a = kb + r（a，b，k，r皆为正整数，且r不为0）
假设d是a,b的一个公约数，即a和b都可以被d整除。
而r = a - kb，两边同时除以d，r/d=a/d-kb/d，由等式右边为整数，可知等式左边r/d也为整数
因此d也是 b , r 的公约数。
可推广到任意d1,d2......若是a，b的公约数，则也是b，r的公约数，即(a，b)和(b，r)的公约数相同
因(a，b)和(b，r)的公约数相同，则其最大公约数也相等，得证。
注（可以这样理解）：既然a，b与b，r有相同的公约数，那么其中最大的公约数也是相同的，即求a，b的最大公约数可转化为求b，r的最大公约数
（5）c++代码实现
#include <iostream>
using namespace std;
int main(void){int a,b;cin>>a>>b;while(a%b!=0){int temp=a%b;a=b;b=temp;}printf("%d\n",b);return 0;
}二、__gcd函数
用c++的iostream头文件的时候,要加上algorithm
具体代码：
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){int a,b;cin>>a>>b;printf("%d\n",__gcd(a,b));return 0;
}2.最小公倍数
由最大公约数得：lcm(a,b)=a/__gcd(a,b)*b
具体代码
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){int a,b;cin>>a>>b;printf("%d\n",a/__gcd(a,b)*b);return 0;
}相关例题：力扣878：第N个神奇数字
具体实现代码：
class Solution {
public:int nthMagicalNumber(int n, int a, int b) {long long m=(long)n*min(a,b); //这里一定要（long）n*min(a,b),否则过不了long long l=1,r=m,res;while(l<=r){long long mid=l+(r-l)/2;if(check(mid,a,b)>=n){res=mid;r=mid-1;}else{l=mid+1;}}return res%1000000007;}int check(long long x,long long a,long long b){return x/a+x/b-x/lcm(a,b);}};3.同余定理
这里先介绍+，-，*三个运算，/后续会添加
一、同余定理概念
同余定理(也称为同余关系)是数论中的一个重要概念，它描述了两个整数在某个整数模下的相等关系。具体来说，如果两个整数 a和b除以一个正整数m 后，得到相同的余数，那么我们就说 a 和b在模 m 下同余，记作:
a=b mod m
这表示 a -b能被 m 整除，即存在整数 k，使得 a -b= km。
同余的基本性质包括
1. 自反性:对于任何整数 α，都有 a ≡ a mod m。
2.对称性:如果a≡b mod m,那么b≡a mod m。
3.传递性:如果a≡b mod m且b≡c mod m，那么a≡c
mod m.
4.加法和乘法的封闭性
如果a≡b mod m和c≡d mod m，则a+c≡（b+ d ）mod m和a·c=b·d mod m.
自我理解：两个数同时取余m 再做运算 做完运算的结果也取余m 得到的结果与直接做运算再对结果取余m的结果一样。
二、对应定理具体实现
（1）+法的同余定理
（a+b)%m==(a%m+b%m)%m
（2）-法的同余定理
（a-b)%m==(a%m-b%m+m)%m
（3）*法的同余定理
(a*b*c)%m==(((long)(a*b)%m)*c)%m
注意：
为了不溢出，我们知道两个int类型的的相乘不会溢出long，于是我们把相乘的中间得到的结果用强制类型转换，转成long
减法如果不加+m,结果可能是负数，但一般题目都会要求得到非负的取模后的结果
