目录
最大公因数gcd(a,b)和最小公倍数lcm(a,b)的关系
欧几里得算法
辗转相除法
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}其他几种求最大公因数的方法：最大公因数
最大公因数gcd(a,b)和最小公倍数lcm(a,b)的关系:
gcd(a,b)*lcm(a,b)=a*b
注意求最小公倍数时要写成a/gcd(a,b)*b,否则若先相乘可能数据会越界
扩展欧几里得算法
先了解一下贝祖定理
贝祖定理
对于两个整数?a、b，若gcd(a,b)=c，等价于方程?ax+by=c有整数解。
特别地，两个整数?a、b互质时，等价于方程?ax+by=1有整数解
扩展欧几里得算法
找出一对整数(x,y)，使得ax+by=gcd(a,b)。
可利用gcd(a,0)=a，找出(x,y)的一对解
代码一：
int ex_gcd(int a, int b, int& x, int& y)//返回值是gcd(a,b)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
int d = ex_gcd(b, a % b, y, x);//注意x,y的顺序变了
y -= (a / b) * x;
return d;
}代码二：
void ex_gcd(int a, int b, int& d,int& x, int& y)//d是a和b的最大公因数
{
if (!b) { d = a; x = 1; y = 0; }
else { ex_gcd(b, a % b, d, y, x); y -= x * (a / b); }
}通过上述代码，我们求出了ax+by=gcd(a,b)的一组解(x1,y1)，任取另外一组解(x2,y2)，则ax1+by1=ax2+by2，得a(x1-x2)=b(y2-y1)，两边同时除以gcd(a,b)得a′(x1-x2)=b′(y2-y1)，其中a′=a/gcd(a,b)，b′=b/gcd(a,b)，此时a′和b′互素，因此x1-x2一定是b′的整数倍。设它为kb′，计算得y2-y1=ka′。(该证明过程来自《算法竞赛入门经典》)
由此得出：
设a,b,c为任意整数，若方程ax+by=c的一组整数解为(x?，y?)，则它的任意整数解都可以写成(x?+kb′，y?-ka′)，其中a′=a/gcd(a,b)，b′=b/gcd(a,b)，k取任意整数。
此外：
设a,b,c为任意整数，方程ax+by=gcd(a,b)的一组解是(x?，y?)，则当c是gcd(a,b)的倍数时ax+by=c的一组解是(x?*c/gcd(a,b)，y?*c/gcd(a,b))，当c不是g的倍数时无整数解。
唯一分解定理
唯一分解定理又称为算数基本定理。
唯一分解定理定义：
任何一个大于1的自然数?N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积，即
例如：72不是质数，可这样分解：72=2^3*3^2;
唯一分解定理的应用：
1.求数N的因子个数
对于正整数N，它的正因数个数为(1+a1)*(1+a2)*(1+a3)*…*(1+an)
? ? ? ? 当正因数个数等于2N时，称为完全数，是否存在奇完全数，至今仍是一个未解决的猜想
2.求所有正因数之和
(q1^0+q1^1+q1^2.....q1^a1)*(q2^0+q2^1+q2^2.....q2^a2)*...*(qn^0+qn^1+qn^2.....qn^an)
3.求gcd(最大公因数)和lcm(最小公倍数)
4.证明根号2是无理数
5.证明素数个数无限
Eratosthenes筛法
当构造1~n的素数表，直接枚举判断会超时，此时就用到了Eratosthenes筛法
对于不超过n的每个非负整数p，删除2p,3p,4p……，处理完后还没有被删除的数就是素数，时间复杂度为O(nlogn)
memset(vis, 0, sizeof(vis));//初始化数组，最后数组中为零的就是素数
for (int i = 2; i <= n; i++) {
for (int j = i * 2; j <= n; j += i) {
vis[j] = 1;
}
}那么，我们再来想，对于第一次i=2，我们筛掉了2的倍数（除2外），呢我们在筛4的倍数，6的倍数…就可以直接跳过，由此，我们我们可以在第一次循环结束后加一个判断if(!vis[i])，这样便能筛掉已经判断过的情况，优化代码如下:
memset(vis, 0, sizeof(vis));
for (int i = 2; i <= sqrt(n); ++i) if (!vis[i])
for (int j = i * i; j <= n; j += i) vis[j] = 1;注意在使用时1要特判一下
素数定理??
π(x)~x/lnx，π(x)表示不超过x的素数的个数，π(x)和x/lnx两者近似相等，精度在基础算法中已足够
同余
同余含义
????????a≡b(modn)的含义是"a和b关于模a同余"。
同余就是余数相同，例如13和18除以5的余数相同，就说13和18模5同余，记作13≡18(mod5)
运算性质：
1.( a + b ) mod n = ( ( a mod n ) + ( b mod n ) ) mod n
2.( a - b ) mod n = ( ( a mod? n ) - (b mod n ) + n) mod n
3.a * b mod n = ( a mod n ) * ( b mod n ) mod n
在减法中，由于amodn可能小于bmodn，因此需要在结果加上n，在乘法中，要注意相乘时数据可能溢出的问题
大整数取模，幂取模，横线性方程组问题戳→数论-同余与模算数
数根小知识：
将一个正整数的各个数位的数字求和，直到和为一位数为止，这个数被称为原数的数根。
一个数的数根就是它除以9的余数（注意数根为9时例外，此时原数除以9余数0）
两个正整数数根相同，意味着它们两个除以9的余数相同。
积性函数
积性函数：
对于任意互质的整数a和b有性质f(m*n)=f(m)*f(n)的数论函数。
完全积性函数：
对于任意整数a和b有性质f(m*n)=f(m)*f(n)的数论函数。
欧拉函数
定义
对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目（因此φ(1)=1）。
????????例如φ(8)=4，因为1,3,5,7均和8互质。
公式：
????????
性质：
1.对于质数p，φ(p)=p?1
2.欧拉函数是积性函数，但不是完全积性函数。若m,n互质，则φ ( m ? n ) = φ ( m ) ? φ ( n ) φ(m*n)=φ(m)*φ(n)φ(m?n)=φ(m)?φ(n)。特殊的，当m=2，n为奇数时，φ(2*n)=φ(n)。
3.当n>2时，φ(n)是偶数。
4.即n的因数（包括1和它自己）的欧拉函数之和等于n。
5.小于n的数中，与n互质的数的总和为：φ(n) * n / 2 (n>1)
以上欧拉函数性质来源于博客欧拉函数，里面有详细证明
欧拉定理
定义：设a,n∈N+，且gcd(a,n)=1,则
gcd(a,n)=1是说a和n互质，φ(n)是指欧拉函数
费马小定理
若a与n互质，且n为质数，则
当n为质数时，根据欧拉函数性质一，φ(n)=n?1，所以费马小定理实质上是欧拉定理的一种特殊情况
逆元
公式：
????????
????????即a^(P-2)modP等价于(1/a)modP
由来：
根据费马小定理
两边同时除以a，得到
当然要注意在费马小定理中a和n互质
求逆元的代码，注意逆元符号是inv
int POW(int a, int b)//快速幂
{
int ans = 1;
while (b) {
if (b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
int inv(int x) {//求逆元
return POW(x, mod - 2);
}愿诸位早日成为数论大佬
完结撒花(*^▽^*)