数论整理

· · 个人记录

数论常用知识整理

1.整除理论

整除是数论的基础，所以我们从整除有关的只是开始讲。

1.1 整除的基本性质

传递性：若a|b，且b|c，则a|c

可加性：若a|b，且a|c，则a|(bx+cy)

可乘性：若a|b，且c|d，则ac|bd

（我才不会告诉你们这些都是我自己瞎起的名字）

判断两数相等：若a|b，且b|a，则a=b

从整除得出的不等式：若a|b，则a\le b

1.2 最大公约数与最小公倍数

定义就不说了~

常用的性质：

1.\ gcd(a,b)\times lcm(a,b)=a\times b

这个性质只适用于两个数，对多个数并不适用（随手就能够构造出一组反例）

它在数论中常常用于将lcm转化为gcd，在后面的例题中也有用到

2.\ $若$a|c$，且$b|c$，则$lcm(a,b)|c\ $。特别的，若$gcd(a,b)=1$，则$ab|c 3.\ $若$a|b$，且$a|c$，则$a|gcd(b,c)\ $。特别的，若$gcd(b,c)=1$，则$a=1

这两个性质的很好理解，他们主要的应用是后面的部分。

1.3 裴蜀定理

1.3.1 定理内容
对于任意两个整数，它们的最大公约数必能表示为这两个数的线性组合。

用数学语言来表示就是：\forall a,b\in Z,\exist x,y\in Z,gcd(a,b)=ax+by

这个定理的证明就用到了辗转相除，也就是对于形如ax+by=c的式子，我们令a'=b,b'=a\%b，重新得到一条式子，然后一直迭代下去，直到b=0时为止，容易证明最后一条式子中的c就是最初的a和b的最大公约数（因为在辗转相除的过程中，有gcd(a,b)=gcd(b,a\%b)）。

这种方法就可以用来求两个数的gcd，同时再根据相邻两条式子中a,b与a',b'的关系，就可以求出不定方程ax+by=gcd(a,b)的一组特解(a_0,b_0)了。

1.3.2 定理推广
也就是说，$ax+by$不能表示为$1\thicksim gcd(a,b)-1$中的数。 证明也很显然，因为$a,b$都是$gcd(a,b)$的倍数，而$1\thicksim gcd(a,b)-1$中的数显然都不是$gcd(a,b)$的倍数。 以上的定理对于任意$n$个整数都是适用的，也就是说，对于任意$n$元整数组，它们的$gcd$都可以表示为这$n$个数的线性组合，且是这$n$个数的线性组合中的最小正整数。 由此我们就可以非常开心的切掉[小凯的疑惑](https://www.luogu.org/blog/jszjinshengzhi/luogu-p3951-xiao-kai-di-ni-huo-2017-tg-day1-t1-post)这题了~（逃 ### 2 同余理论 #### 2.1 同余的基本性质 （以下没有注明模数的都默认模数为同一个整数。） 传递性：若$a\equiv b$且$b\equiv c$，则$a\equiv c

可加性：若a\equiv b，且c\equiv d，则ax+cy\equiv bx+dy

可乘性：若a\equiv b，且c\equiv d，则ac\equiv cd

2.2 费马小定理&欧拉定理

2.2.1 欧拉定理与欧拉函数

欧拉函数：\varphi(n)表示模n的剩余系中，缩系的个数。

这样讲太MO化了？那我们换种说法。

欧拉函数：\varphi(n)表示1\thicksim n-1，中与n互质的数的个数。

定理内容：若gcd(a,p)=1，则a^{\varphi(p)}\equiv 1\quad(mod\ p)

2.2.2 费马小定理

若p为质数，且p\nmid a，则a^{p-1}\equiv 1\quad(mod\ p)

费马小定理相当于欧拉定理的特殊情况，因为\varphi(p)=p-1，于是就很容易从欧拉定理推导过来了。

但是呢，这个定理却经常比欧拉定理更加有用。

为什么呢？因为p-1好求，而\varphi(p)难求，而且在大多数题目中模数也都是质数。

比如说，在用快速幂求a^b时，我们基本上只会对底数a取模。但是如果b也很大呢？我们也能将b模上一个p吗？显然不能，but，我们可以将b模上p-1，这样就可以保证指数也不会大到炸long\ long。

2.3 中国剩余定理（XX定理）

2.3.1 中国剩余定理
是你！ （逃 咳咳咳，皮完了，开始讲正题。 定理内容： 对于一元线性同余方程组 $x\equiv a_1\quad(mod\ m_1) x\equiv a_2\quad(mod\ m_2) x\equiv a_3\quad(mod\ m_3) ... x\equiv a_n\quad(mod\ m_n)

若模数m_1,m_2,m_3,...,m_n两两互质，则在模M意义下x有且仅有一个解：x=(\sum_{i=1}^na_it_iM_i)\quad (mod\ M)

这里M=\prod_{i=1}^nm_i,M_i={\frac M{m_i}},t_i=M_i^{-1}\quad (mod\ m_i)

这个具体的解其实并没有什么卵用，因为并不会有什么题目会直接让你无脑计算这种一元线性同余方程组的解，但是它可以用来证明方程组在1\thicksim M范围内恰有一个解。

还记得九校联考第一场Day2\ T2\ Division吗？其中有一步就是用这个性质推导的，下面会讲到。

2.4 阶

2.5.1 什么是阶

若gcd(a,m)=1，则必有无数多个r使a^r\equiv 1\quad(mod\ m)，其中最小的r成为a模m的阶，常记为d。

2.5.2 阶的性质

若a^r\equiv 1\quad(mod\ m)，则d|r。反过来也是成立的。

这条式子是不是特别眼熟？

没错，就是它，费马小定理和欧拉定理！

具体例子看题目吧~

2.5.3 原根

这个东西嘛，我自己也不怎么会，而且感觉NOIP中没什么用，那就跳过吧。（逃

3. 筛法

3.1 素数筛法

3.1.1 暴力筛

就是O(n\sqrt n)的无脑筛，不讲。（逃

3.1.2 埃氏筛

这种筛法也比较暴力，就是从1开始一个个数枚举，如果一个数是素数，那么就将它的倍数一个个打标记。如果一个数没被打过标记，那么它就是素数。复杂度：O(n\ log(log(n)))，一般可以当线性处理（只要这个出题人够良心）。

很无脑，是不是？

3.1.3 欧拉筛

在埃氏筛中，我们发现一个数可能会被它所有的质因子都筛一遍，这样岂不浪费？我们能不能让每个数都只被筛一次？

嗯，还真能，欧拉筛就行。

欧拉筛跟埃氏筛很像，但是每个数只能被它最小的质因子筛掉，于是复杂度就是稳O(n)了。

3.2 积性函数

在数论函数中，有一种函数具有一种美丽的性质：\forall a,b,gcd(a,b)=1,f(a\cdot b)=f(a)\cdot f(b)

这类函数叫作积性函数。

还有一种数论函数，满足\forall a,b,f(a\cdot b)=f(a)\cdot f(b)，它们叫作完全积性函数。

完全积性函数看起来很厉害是不是？是不是？

其实没卵用

一般的题目基本上只用到积性函数，因为积性函数有一个超级美妙的性质：

它可以用欧拉筛来筛！

然后一些问题就可以很开心的解决了~

3.3 狄利克雷卷积

啥，dikeleisi？

定义数论函数f(x)和g(x)的狄利克雷卷积为：

(f\cdot g)(n)=\sum_{d|n}f(d)\cdot g(\frac nd)

性质：若f,g均为积性函数，则f\cdot g也为积性函数。

特殊的，若f为积性函数，则\sum_{d|n}f(d)也为积性函数

常见的积性函数：\varphi,\mu...

具体看题目吧~

4. 整除分块