数论学习笔记(I)

respect_lowsmile

2022-06-27 18:27:44

Personal

数论(根本不会)

为啥不学高级数据结构而学数论啊

文章纯粹照搬PPT。。。。。。

素数与约数

1.算数基本定理

任何一个大于1的正整数都能唯一分解成有限个质数的乘积

写作:

n=p_1^{c1}p_2^{c2}······p_m^{cm}

可以直接写作:

\prod_{i=1}^mp_i^{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