[Pinned]合集-证明

合集-证明

---

一些关于基础的零散证明。
很多东西大胆猜测有风险。。。

---

索引（横向）：

------------------------------	------------------------------	------------------------------
关于$\phi$的线性筛法	组合数奇偶性	$\phi \otimes id_ 0 = id_ 1$
欧几里得算法	$\phi(n)=n\prod_ {i=1} ^l (1- \frac{1}{p_ i})$	$\lfloor \frac{a}{bc} \rfloor=\lfloor \frac{\lfloor \frac{a}{b} \rfloor}{c} \rfloor$
线性预处理逆元	$\sum_ {i=0}^ n(^ {i+r}_ i)$

---

关于$\phi$的线性筛法

---

组合数奇偶性：
$(^n _ k)=(n\&k==k)$
证明见$lucas$

---

$\sum_ {i|x}\phi(i)=id_ 1(x)$
($\phi \otimes id_ 0 = id_ 1$)
这里就是把1~n-1/n的所有数列出来。
$\frac{1}{n},\frac{2}{n},\frac{3}{n},\frac{4}{n},\frac{5}{n},...$
($n=6$时原数列为$\frac{1}{6},\frac{1}{3},\frac{1}{2},\frac{2}{3},\frac{5}{6}$)

假如说$n$与某个数$i$有$gcd(i,n)>1$，那么他可以和$n$同时除掉这个$gcd$
然后这样就得到了一个新的数列，其中分子与分母互质。
对于任何一个小于$n$的$i$,$\frac{i}{n}$一定可以被化简成分母为$n$的因数的一个最简分数
对于任何一个$i\|n$的$i$，与$gcd(i,j)==1\&j<i$的$j$构成的分数$\frac{j}{i}$也一定能找到与之相等的$\frac{k}{n}$
所以就相等了

---

欧几里得算法: $gcd(a,b)=gcd(b,a\%b)$
设$a>b$且$a=kb+r,c=gcd(a,b)$
则$a=nc,b=mc$
$r=a-kb=nc-kmc=(n-km)c$

一个结论：$gcd(n-km,m)=1$
如果有公因数，设$n-km=xd,m=yd(d>1)$
$n=km+xd=kyd+xd=(ky+x)d$
这样的话：
$a=nc=(ky+x)cd,b=mc=ycd$
所以$gcd(a,b)=gcd(ky+x,y) \times cd>c$，与$gcd(a,b)=c$不符。

有上面那个结论得到$gcd(b,r)=gcd(mc,(n-km)c)=c=gcd(a,b)$

---

$\phi(n)=n\prod_{i=1} ^l (1- \frac{1}{p_ i})$
（设$p_ i(1\leq i \leq l)$为$n$的质因数）

因为$n=\prod_ {i=1} ^l p_ i ^{k_ i}$
而且当$a,b$互质时，有$\phi(a * b)=\phi(a) * \phi(b)$
所以$\phi(n)=\prod_ {i=1} ^l \phi(p_ i ^{k_ i})$

又$\phi(p^k)=p^k-p^{k-1}=p^k(1-\frac{1}{p})$
$\phi(n)=\prod_ {i=1}^l p_ i^k(1-\frac{1}{p_ i})=n\prod_ {i=1}^l(1-\frac{1}{p_ i})$

---

$\lfloor \frac{a}{bc} \rfloor=\lfloor \frac{\lfloor \frac{a}{b} \rfloor}{c} \rfloor$

右边很显然不可能比左边大
设$a=kbc+d(d<bc)$

$\lfloor \frac{\lfloor \frac{a}{b} \rfloor}{c} \rfloor=\lfloor \frac{kc+\lfloor \frac{d}{b} \rfloor}{c} \rfloor \leq k+\frac{\frac{d}{b}}{c}$
根据定义，有$(d<bc)$，所以
$\lfloor \frac{a}{bc} \rfloor=k=\lfloor k+\frac{\frac{d}{b}}{c} \rfloor$

---

线性预处理逆元：
现在要求一个数$i$对于质数$P$的逆元。
$P=\lfloor \frac{P}{i} \rfloor \times i+P\%i$
$\lfloor \frac{P}{i} \rfloor \times i+P\%i=0(\mod P)$
两边同时乘上$i$的逆元和$P\%i$的逆元
$\lfloor \frac{P}{i} \rfloor \times (P\%i)^{-1}+i^{-1}=0(\mod P)$
$i^{-1}=-\lfloor \frac{P}{i} \rfloor \times (P\%i)^{-1}(\mod P)$

---

$\sum_ {i=0}^ n(^ {i+r}_ i)$（或$\sum_ {i=0}^ n(^ {i+r}_ r)$）
组合意义是前面r个球，后面n个球，在后面n个球中选一个球作为右界，前面取r个球的方案数。

或者可以在前面加上一个值为0的$(^ r_ {-1})$
根据组合数递推公式我们能够得到：

$$(^ r_ {-1})+\sum_ {i=0}^ n(^ {i+r}_ i)=(^ r_ {-1})+(^ r_ 0)+\sum_ {i=1}^ n(^ {i+r}_ i)=(^ {r+1}_ 0)+\sum_ {i=1}^ n(^ {i+r}_ i)=\cdots=(^ {r+n+1}_ n)$$