【OI之路】11更高级数论-1定理杂烩

数论定理杂烩

费马小定理

条件:质数p,gcd(a,p)=1
结果:$a^{p-1}=1 (\mod p)$
顺便提一下,如果使用$a^p=a (\mod p)$的形式,不需要满足gcd(a,p)=1
证明:不会
应用:
1.求逆元:【OI之路】11更高级数论-2逆元
2.某些数据范围巨大的题目如
Gauss Fibonacci
矩阵游戏

欧拉函数与欧拉定理

欧拉函数:对于正整数n,代表小于等于n的与n互质的数的个数,记作$\phi(n)$
欧拉定理:

  1. 如果n为某一个素数p,则$\varphi(p)=p-1$
  2. 设$n=p1^{a1}\times p2^{a2} ……\times pk^{ak}$,
    那么$\varphi(n)=n\times \frac{p1-1}{p1}\times \frac{p2-1}{p2}……\times \frac{pk-1}{pk}$
  3. 如果n为某一个素数p的幂次,那么$\varphi(p^a)=(p-1)\times p^{a-1}$
  4. 如果n为两个数a和b且满足gcd(a,b)=1的积,那么$\varphi(a\times b)=\varphi(a)\times \varphi(b)$ 【所以是积性函数】
  5. 当gcd(a,m)=1,$a^{\varphi(m)}=1 (\mod m)$
  6. 对于n>1,1~n中与n互质的数的和为$n \times \varphi(n)/2$
  7. $\sum_{d|n} \varphi(d) = n$
  8. 当$gcd(a,p)=1$时,满足$a^x=1 (mod p)$的最小正整数x一定是$\varphi(p)$的约数

证明:

  1. 显而易见
  2. 容斥原理?不会
    Up 2018.8.6 其乘积如果展开,就是对于素数p倍数的容斥
  3. 由定理2得出
  4. 由定理2得出
  5. 不会
    Up 2018.8.6 这个东西
  6. 这个证明灰常有趣
    因为$gcd(n,x)=gcd(n,n-x)$,可以看作是一对,则每一对的和都是n
  7. 不会
  8. 运用反证法
    假设存在最小的x0,不是其约数,则$\varphi(p)=t \times x0 + r (0<r<x0)$
    那么因为$a^{x0}=1 (\mod m)$,$a^{t \times x0}=1 (\mod m)$
    又因为$a^{\varphi(m)}=1 (\mod m)$,所以$a^r=1 (\mod m)$
    这与x0的最小相矛盾。

线性筛:

  1. $\varphi(p)=p-1$ 【p是素数】
  2. $\varphi(p\times i)=p\times \varphi(i)$【p%i==0】
  3. $\varphi(p\times i)=(p-1)\times \varphi(i)$【p%i!=0】

等比数列二分求和(好吧其实不是定理)

神不神奇~不算难,但不好想
举例:$S=A+A^2+A^3+…+A^k$
采用分治的思想:

  1. k=1,$S_k=A$
  2. k%2=0,$S_k=(1+A^{k/2})\times (A+A^2+A^3+…+A^{k/2})$
  3. k%2=1,$S_k=S_{k-1}\times A^k$
    有木有一种熟悉感?没错,FFT的快速也是靠这个分治减少带入计算量!
    题目如Matrix Power Series

威尔逊定理

万一派得上用场?
当p是质数
$ (p-1)! = -1 (\mod p) $
$ (p-1)!\mod p = p-1 $

二项式定理

也可参阅组合数学一章
$$
(a+b)^k=
\sum_{i=0}^k
C_n^i \times
a^i \times
b^{n-i}
$$

差比数列

每一项,可以拆分为等差数列和等比数列
据说是高中常用知识……

形如$S_n=a+A(a+d)+A^2(a+2d)…+A^n(a+nd)$
参考等比数列中乘以A-1
$$
(A-1)S_n=-a+Aa-A(a+d)+A^2(a+d)-A^2(a+2d)…A^n(a+(n-1)d)-A^n(a+nd)+A^{n+1}(a+nd)
$$

$$
(A-1)S_n=-a-nAd+A^{n+1}(a+nd)
$$

$$
S_n=\frac{A^{n+1}(a+nd)-a-nAd}{A-1}
$$

神仙欧拉的另一个公式

本公式属于拓扑学的研究范围
不过之前做一道planar的题目用到过

对于一个平面图,一定满足$m \leq 3n-6$

原公式:点数n+面数r-边数m=联通块数量cnt(当做无向图)+1
对于当前的平面图判定,每条边最多给两个面使用,每个面至少有3条边
也就是说,$r \leq \frac{2m}{3}$
原式化为 $m=n+r-cnt-1$ 后带入,得到 $m \leq n+\frac{2}{3} m -cnt-1$
$3m \leq 3n+2m-3cnt-3$
显然cnt最小为1,则 $m \leq 3n-6$

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/a06a.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%