笔记罢了、、、

[AnteAntibe_LHP]

数学

整除 以及 取模

定义 c = a/b\\ a = b*c\\ 除法永远要以乘法的逆运算来理解，由第二个式子去找到第一个式子\\ 这个理解方式便于理解逆元等运算

一些整除的性质


辗转相除法：实际上就是

gcd(a,b) = gcd(b, a \% b)\\

这个东西的时间复杂度是 O(\log(n)) 证明其实很简单：

每次进行辗转相处至少除以2，也就是结果至多缩小到原来的n/2.因此是(logn)

分解质因数：pollard rho算法——时间复杂度是O(n^-4)的分解质因数算法

可以贷款会，平时不用会，考前背个板子就好了

一个数字n的质因子大概有 n / \log(n) 个，这只是一个数量级，没有证明

一般求质数，我们就筛掉合数，得到如下↓ 去筛的数基本上是质数


我们可以使用一种全新的方法去理解取模

l \% p \\ 我们将其看作一个\% p的数域: 0,1,...,p-1 \\ 定义加法：3+5 = 1 (mod 7意义下) \\ 这个东西加法结合律交换律，乘法的这些定律……都是满足的 \\ 所有东西都在模意义下讨论 在模p意义下永远没有 p+1这个数字：它和1根本没有任何区别


在取模意义下，有了同余的概念 同余符号就是mod m意义下的等号

一些性质↓


逆元：就是mod意义下的除法而已

这是一个扩欧——逆元的证明——

n/a = m \ (mod\ p)\\ ax = 1\ mod\ p\\ n = am\ (modp)\\ nx = m\\ \\ ax= 1/(mod\ p)\\ ax + py =1\\ ax + py = gcd(a,p)\\ a_x + p_y = 1\\ \\ b = a + nc\\ k|a , k|b , k|c b/k = a/k + m*(c/k) \\ {(a + kg) \mod p|p 是自然数}\\ p / gcd(p,g)\\

组合数取模： C(n,m)

• 若p是质数，使用Lucas定理。
• 若p不是质数，分解质因数CRT起来
• CRT:给出%a意义下是多少 %b意义下是多少……将这些东西还原回去


exgcd可以不用是质数。 预处理多个逆元一般用线性递推求逆元

费马小定理：

定理一：\\ 若p为质数，且a不为p的倍数，则 a^{p-1} = a(\mod p) \\ 所以说 a^{p-2} 就是\%p意义上的逆元，但是p要是质数



费马小定理——Miller-Rabin素性检验


一篇好博客

欧拉函数


1-n\\ n-(1-1/p_1)*n-(1-1/p_2)*n-...-(1-1/p_k)-(1-1/p_1p_2)*n\\ 剩下这么一些数\\ 画出来是独立出来的，所以需要容斥原理证明\\


欧拉函数具有积性：

\phi(n) = n \times \left(1-\frac{1}{p_{n1}}\right) \times \left(1-\frac{1}{p_{n2}}\right) \times ... \times \left(1-\frac{1}{p_{nk}}\right)\\ \phi(m) = m \times \left(1-\frac{1}{p_{m1}}\right) \times \left(1-\frac{1}{p_{m2}}\right) \times ... \times \left(1-\frac{1}{p_{mk}}\right)\\ \phi(nm) = nm \times \left(1-\frac{1}{p_{n1}}\right) \times \left(1-\frac{1}{p_{n2}}\right) \times ... \times \left(1-\frac{1}{p_{nk}}\right)\times \left(1-\frac{1}{p_{m1}}\right) \times \left(1-\frac{1}{p_{m2}}\right) \times ... \times \left(1-\frac{1}{p_{mk}}\right)\\

知道是积性函数后

a = i*p[j]\\ i\%p[j] = 0\\ 有 \phi(1)...\phi(i)\\ \phi[a] = \phi[i] * \phi[p[j]]\\ a = p ^ k\\ \phi [a] = a*(1-1/p)\\ i\%p[j] = 0\\ \phi[a] = \phi[i]*p[j]\\

所以说若f是积性函数 只需要知道 f(p^k) ，就可以知道1-k之间这个函数所有的取值

知道其之后 f(1) … f(n)可以全部算出来

求法：


（不会证明没有关系，记住欧拉定理就好了

裴蜀定理


ax + by = gcd(a,b)\\ ax_1 + by_1 = 1\\ by_1 = 1(mod a)\\ 0-(a-1)

↓

EXGCD:


a,b,x2,y2全部都知道 这样就可以表示出x1,y1

用递归就可以以一个式子将x1,y1表示出来

CRT中国剩余定理



扩展中国剩余定理：根本不去管他，耶！

筛子


二项式定理：

(a+b)^n = (a+b)*(a+b)*...\\ 每一个都选a或者选b\\ \sum_{i=1}^na^i*b^{n-1}\\ 然后还要选个系数 \sum_{i=1}^na^i*b^{n-1}*C_n^m\\

(好像发现了什么初一就推过的东西？)

---


（这个不是上次做过的结论题吗

答案就是n/k 入门题

---


n\ mod\ k \\ k = n-k*[n-k]\\ 拆开来 ，求和起来，树论分块就可以了，

---


做法一：分解质因数，桶里塞栈，预处理每个点的答案。走到询问的点分解质因数，找到栈里顶端的这个结点就可以了

做法二：虽然听不懂。但是我们可以将含有每个因数的点建个虚树，然后问题就是这样虚树有多大。

做法三：随便找两个点，暴力往上爬并染色，再找第三个点继续，这样就是O(n)的染色，或者也可以树剖+线段树变成O(logn)。

---


就是组合数罢了，等下我贴个公式

[胡瑜辰]

好经典的初一就推过！我记得数学书里还有这个哈哈。
膜拜安特安泥巴%%%
以及你图片没传上来

[AnteAntibe_LHP]

是这样的 并且我懒（）

[白桐吉 (■ ꧁༻残缺ぁ神迹々龙つ随风༻꧂)]

膜拜！点赞但点不了

[白桐吉 (■ ꧁༻残缺ぁ神迹々龙つ随风༻꧂)]