平淡无奇的数论笔记

前言

有时候会把最基本的定义忘掉……
当且仅当存在一个正整数c使得a × c = b，则正整数a是正整数b的因子。

C99规定，对非负整数取模的结果为非负整数，否则为负整数。
贝祖定理

取整问题

double->int:

$x\le yx<\lfloor y\rfloor +1$
$x>yx\ge \lfloor y\rfloor +1$
$ac\le b⟺a\le \lfloor \frac{b}{c}\rfloor$
$ac\ge b⟺a\ge \lceil \frac{b}{c}\rceil$
$ac<b⟺a<\lceil \frac{b}{c}\rceil$
$ac>b⟺a>\lfloor \frac{b}{c}\rfloor$
$ifa\le x<blen(x)=\lfloor b\rfloor -\lfloor a\rfloor$

上整->下整

$\lceil \frac{y}{x}\rceil =\lfloor \frac{y-1}{x}\rfloor +1orceil(\frac{y}{x})=\frac{y-1}{x}+1$

左零右开区间奇偶数个数

$$\begin{gathered} if0\le x<b \\ count(x,奇数)=\lfloor \frac{b}{2}\rfloor orx>>1 \\ count(x,偶数)=\lfloor \frac{b+1}{2}\rfloor orx+1>>1 \end{gathered}$$

（写公式真累）

欧几里得和拓展欧几里得

$(a,b)=d(d|a,d|b)$
$b|a$，则$(a,b)=b\times 1+a\times 0$
否则令$a=b\times d+r(r!=0)$
$r=a-b\times d$
$(a,b)|a,(a,b)|b$
$(a,b)|r$
欧几里得：$(a,b)=(b,r)$
令$d=\lfloor a/b\rfloor ,r=a\%b$
$(a,b)=(b,a\%b)$
$b|a$，则$(a,b)=b\times 1+a\times 0$
$a\%b=a-b\times \lfloor a/b\rfloor$
拓展欧几里得：$(a,b)=(a-\lfloor a/b\rfloor \times b)\times 1+b\times 0$
（不太严谨）

逆元（拓展欧几里得法）

ax≡k（mod b）（ax+by=k）

来源：OI Wiki

线性逆元

$1^{-1}\equiv 1(modp)$(p为质数)
$p=d\times i+r（d=\lfloor \frac{p}{i}\rfloor ,r=p\%i）$
$p\equiv 0(modp)$
$d\times i+r\equiv 0(modp)$
$d\times r^{-1}+i^{-1}\equiv 0(modp)$（两边乘$r^{-1}{i}^{-1}$）
$i^{-1}\equiv -d\times r^{-1}(modp)$
$i^{-1}\equiv -\lfloor \frac{p}{i}\rfloor \times (p\%i{)}^{-1}(modp)$
（注意最小正整数$(inv\%p+p)\%p$）

中国剩余定理

下面把这个问题一般化：假设整数
两两互素，则对于任意的整数
，方程组
都存在整数解，且若
都满足该方程组，则必有
，其中
。具体而言，
。

关于GCD

1. GCD递推式：GCD(a,b)=GCD(a,a%b)

2. GCD(a,a-b)=GCD(a,b)

证：GCD(a,b-a)=GCD(a,(b-a)%a)=GCD(a,(b-a+a)%a)=GCD(a,b%a)=GCD(a,b)
应用：CF1110C Meaningless Operations

算术基本定理（唯一分解定理）

1. 一个大于1的正整数N，如果它的标准分解式为：
   ，那么它的正因数个数为
   ，它的全体正因数之和为

2. P=1+p+p^2+…+pn二分递推求解：
   ①n为奇数：

欧拉函数性质

$\phi (n)->\phi (nm)$

m为质数

$n\mid m时,\phi (nm)=\phi (n)\times m$
$n\nmid m时,\phi (nm)=\phi (n)\times (m-1)$

n,m互质

$\phi (nm)=\phi (n)\times \phi (m)$

其他情况

分解因子（大概）

组合数学

所有质因数序列排列组合

例题
$设x=p_0^{a_0}{p}_1^{a_1}{p}_2^{a_2}\cdots p_n^{a_n}$
$排列组合=\frac{({\sum }_{j=0}^n{a}_j)!}{{\prod }_{i=0}^n(a_i!)}$

几何分布

记每次试验中事件A发生的概率为p，试验进行到事件A出现时停止，此时所进行的试验次数为X，其分布列为：
譬如，某产品的不合格率为0.05，则首次查到不合格品的检查次数X ～ GE(0.05) 。
（1）为得到1次成功而进行n次伯努利试验，n的概率分布，取值范围为1，2，3，…；
这种情况的期望和方差如下：


（2）m = n-1次失败，第n次成功，m的概率分布，取值范围为0，1，2，3，…。
这种情况的期望和方差如下：


比如，假设不停地掷骰子，直到得到1。投掷次数是随机分布的，取值范围是无穷集合{ 1, 2, 3, … }，并且是一个p= 1/6的几何分布。

不相交路径

设$(a,b)$为$a$到$b$的路径条数
则$(a_1或a_2或a_n,b_1或b_2或b_n)$的不相交路径条数为
$$\left|\begin{array}{ccc}{a}_1\times b_1& a_1\times b_2& a_1\times b_n\\ a_2\times b_1& a_2\times b_2& a_2\times b_n\\ a_n\times b_1& a_n\times b_2& a_n\times b_n\end{array}\right|$$