目录
-
前言
-
数论基础
1.1 整除
1.2 带余除法，同余
-
质数
2.1 唯一分解定理
2.2 质数筛（线性筛）
2.3 欧拉函数
-
最大公因数/最小公倍数
3.1 辗转相除法
3.2 裴蜀定理
3.2 扩展欧几里得算法
-
线性同余方程
4.1 费马小定理
4.2 欧拉定理
4.3 逆元
4.4 求解线性同余方程
4.5 中国剩余定理
-
威尔逊定理
-
卢卡斯定理
0. 前言
数论太差了，恶补一下。
学一点更一点。
1.数论基础
1.1 整除
设 \(a\in \N^+\) ，\(b\in \Z\) ，若存在整数 \(q\) 使得 \(b=a\times q\) ，则称 \(b\) 可被 \(a\) 整除，记作 \(a|b\) ，称 \(a\) 为 \(b\) 的因数，\(b\) 为 \(a\) 的倍数。
整除的性质：
- 若 \(a|b\) 且 \(b|c\) ，则 \(a|c\)。
- 若 \(a|b\) 且 \(a|c\) ，则满足 \(a|(b\times x+c\times y)\) ，其中 \(b,c\) 为整数。
- 若 \(m \neq 0\)，则 \(a\,|\,b \iff am\,|\,bm\)
- 若整数 \(x,y\) 满足 \(ax+by=1\) 且 \(a\,|\,n,b\,|\,n\) ，则 \(a\times b\,|\,n\)
- 若 \(b=k\times d+c\) ，则 \(d\,|\,b \iff c\,|\,b\)
1.2 带余除法，同余
若存在整数 \(a,b\)，\(d\) 为给定的整数 ，满足 \(b=q\times a+r,d\leq r <d+|a|\) ，则称 \(r\) 为 \(b\) 除以 \(a\) 的余数。
也可以记作 \(b\equiv r\,(\text{mod}\,\,a)\) 。意味 \(b\) 与 \(r\) 在取模 \(a\) 意义下相等。
同余的性质：
- \(a\equiv b\pmod m,b\equiv c\pmod m\) ，则 \(a\equiv c\pmod m\)
- \(a\equiv b\pmod m\) 则 \(a+c\equiv b+c \pmod m\)
- \(a\equiv b\pmod m\) 且 \(c\equiv d\pmod m\) ，则 \(a\times c\equiv b\times d\pmod m\)
- \(a\times b \equiv k=\) \((a\bmod k)\times(b\bmod k)\)
- 若 \(\gcd(p,q)=1, a\equiv b\pmod p,a\equiv b\pmod q\) ，则 \(a\bmod pq=b\)
2. 质数
设整数 $p\neq 0,\pm1 $，且 \(p\) 没有除 \(1\) 外的其它因数，则称 \(p\) 为质数。
任何一个大于 \(3\) 的质数都可以表示为 \(6k+1\) 的形式
2.1 唯一分解定理
引理：若质数 \(p\,|\,ab\) 则 \(p\,|\,a\) 或 \(p\,|\,b\) 满足其一。
设正整数 \(a\) ，则必有：
\[a=p_1^{e_1}p_2^{e_2}\cdots p_n^{e_n} \]其中 \(p_i\) 为质数，\(e_i\) 为该质数的次数。
在不计次序的情况下，该表示唯一。
2.2 质数筛（线性筛）
我们记 \(f_i\) 标记 \(i\) 是否为质数，\(p_i\) 为已经筛出来的质数。
对于每一个筛出来的质数，我们将它乘上之前筛出的每一个质数，即可筛出所有质数。
为了优化时间，当我们发现这个数曾被筛过便直接跳出循环。
时间复杂度：\(O(n)\)
void work(int n)
{
for(int i=2;i<=n;i++)
{
if(!f[i])
p[++tot]=i;
for(int j=1;j<=tot;j++)
{
vis[i*p[j]]=1;
if(i%p[j]==0) break;
}
}
}
2.3 欧拉函数
定义：\(\varphi(n)=\sum_{i-1}^n [\gcd(i,n)=1]\)。
性质：
- 当 \(n\) 为质数时，\(\varphi(n)=n-1\)。
- \(\varphi(ab)=\varphi(a)\times\varphi(b)\)
- 当 \(n\) 为奇数时，\(\varphi(n)=\varphi(2n)\)
- \(n=\sum_{d|n} \varphi(d)\)
- 将 \(n\) 唯一分解后，\(n=\prod p_i^{e_i}\) 则 \(\varphi(n)=n \times \prod_{i = 1}^s{\dfrac{p_i - 1}{p_i}}\)
线性筛求欧拉函数：
设 \(p_1\) 为 \(n\) 的最小质因子，则：
当 \(\frac{n}{p_1}\bmod p_1=0\) 时，\(\varphi(n)=p_1\times \varphi(\frac n{p_1})\)
否则 \(\varphi(n)=(p_1-1)\times\varphi(\frac n{p_1})\)
标签：数论,质数,varphi,times,学习,pmod,笔记,定理,equiv From： https://www.cnblogs.com/sheeplittlecloud/p/17783619.html