数论学习笔记（I）
respect_lowsmile
2022-06-27 18:27:44
# 数论（根本不会）
~~为啥不学高级数据结构而学数论啊~~
文章纯粹照搬PPT。。。。。。
## 素数与约数
### 1.算数基本定理
任何一个大于1的正整数都能唯一分解成有限个质数的乘积
写作：
$$
n=p_1^{c1}p_2^{c2}······p_m^{cm}
$$
可以直接写作：
$$
\prod_{i=1}^mp_i^{ci}
$$
$pi$ 都是质数且满足 $ p1<p2<······<pm$ , $ci$ 都是正整数。
这玩意。。。好像没啥用，但是后面一些东西都要用到。
### 2.质数分布定理
对于任意正整数 $ x $ ,定义 $ f(x) $ 为不大于 $ x $ 的质数个数，则有 $ f(x)\approx x / ln x $ ，第 $ n $ 个质数的渐近值 $ p(n) \approx n ln n$ 。
~~这个好像真的没啥用~~
### 3.若存在一个正整数 $ n $ 为合数，则存在一个数 $ k $ ,满足 $ 2 $ $ \le $ $k \le $ $ \sqrt{n} $ 且 $ k|n $ 。
证明过程：
首先，我们要证明一个结论：
#### 如果 $m1*m2=n$ ，那么，$ m1 $ 和 $ m2 $ 必定有一个大于 $ \sqrt{n} $，一个小于 $ \sqrt{n} $ 。
然后我们去证明上面的结论，假如我们在 $ 2—sqrt（n）$ 没有找到 $ n $ 的因数，在 $ sqrt(n)—n $ 中找到了因数 $ m1 $ ,根据上面的结论，另一个因数 $ m2 $ 肯定在 $ 2—sqrt（n） $ 之间，与在 $ 2—sqrt（n） $ 之间没有找到因数矛盾，命题获证。
### 4.素数的筛选
#### 1.埃氏筛
原理：素数的倍数一定不是素数
[link](https://img-blog.csdnimg.cn/20181218124213973.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvbGx5X1pfUF9G,size_16,color_FFFFFF,t_70)
#### code
```
for(int i=2;i<=n;++i)
if(isprime[i]==1)
{
for(int j=2*i;j<=n;j+=i)
isprime[j]=0;
}
```
埃氏筛的复杂度已经非常接近线性了，但是不能完全达到线性，因为它在筛的时候会有重复，比如说12，它在被2筛过之后，循环到3，4，6的时候都会再重新筛一遍。
#### 2.线性筛
针对上面的埃氏筛存在的问题，我们可以让每一个合数只被它的最小质因数筛掉。
#### code
```
//v[i]代表i的最小质因数
for(int i=2;i<=n;++i)
{
if(v[i]==0)
v[i]=i,pri[++cnt]=i;
for(int j=1;j<=cnt;++j)
{
if(pri[j]>v[i] || pri[j]>n/i) break;
v[i*pri[j]]=pri[j];
}
}
```
扔下一道例题
[P3383 【模板】线性筛素数](https://www.luogu.com.cn/problem/P3383)
### 5.一个正整数 $ n $ ,至多只有一个大于 $ sqrt(n) $ 的质因子
证明：设 $ p,q≥ sqrt(n) $ ， $ p | n $ , $ q | n $ ,那么我们有 $ pq | n $ , $ pq > n $ , 很显然矛盾，命题获证。
### 6.设 $ a $ , $ b $ 是两个整数，且 $ b != 0 $ ，如果存在整数 $ c $ ,则存在唯一的整数 $ q,r $ , 使得 $ a=qb+r (0\le r < b)$ ，该式被称为带余除法，并记 $ r= a\mod b $ 。
### 7.整除的性质
1. 若 $ a \mid b $ 且 $ a \mid c $ ，则 $ \forall x,y $ ，有 $ a \mid xb+yc $ 。
证明：
设 $ b=an, c=am $ ，则 $ xb+yc=xan+yam=a(xn+ym) $ ，很明显 $ a \mid a(xn+ym) $ ，命题获证。
2. 若 $ a \mid b , b \mid c $ ，则 $ a \mid c $ 。（传递性）
3. 若 $ ma \mid mb (m \ne 0) $ ，则 $ a \mid b $ 。
4. 若 $ a \mid b $ 且 $ b \mid a $ ，则 $ a=\pm b $ 。
### 8.算术基本定理的推论
对于唯一分解的正整数 $ n= p_1^{c_1}p_2^{c_2}……p_m^{c_m} $
其正约数集合可写作 $ \{ p_1^{c_1}p_2^{c_2}……p_m^{b_m}| 0 \le b_i \le c_i \} $
其正约数个数为：
$$
(c_1+1)(c_2+1)……(c_m+1)=\prod_{i=1}^mc_i+1
$$
其所有约数和为：
$$
(p_1^0+p_1^1+……+p_1^{c_i})……(p_m^0+p_m^1+……p_m^{c_m})= \prod_{i=1}^m(\sum_{j=0}^{c_i}a_i^j)
$$
对于一个合数 $ n^2 $ ，它的约数个数为：
$$
\prod_{i=1}^mc_i \times 2+1
$$