数学笔记

一个关于逆元的小技巧

ans = \frac{a}{b}\bmod m = a\bmod \left( {mb} \right)/b

那么下面是证明

\begin{array}{l}\frac{a}{b} = km + x{\rm{ }}\left( {x < m} \right)\\a = kbm + bx\\a\bmod bm = \left( {kbm\bmod bm} \right) + \left( {bx\bmod bm} \right)\\a\bmod bm = bx\\\frac{{a\bmod bm}}{b} = x\\\frac{a}{b}\bmod m = \left( {km\bmod m} \right) + \left( {x\bmod m} \right)\\\frac{a}{b}\bmod m = x\end{array}

为什么我觉得没多大用处……


唯一分解定理

将一个非素数N 唯一分解成有限个素数的乘积

N = \prod\limits_{i = 1}^n {p_i^{{a_{_i}}}}

快速分解:每次只枚举不大于\sqrt {N'}的所有质数(N'\frac{N}{{\prod\limits_{i = 1}^\delta {p_i^{{a_i}}} }},其中\delta是目前枚举到的质数个数 )

可以证明N'只有最多一个超过\sqrt {N'}的质因子。

具体程序如下

 

今天是1月7日,昨天湖南师附集训 宾馆网速40kb/s 本来想传上费马小定理和二次探测定理的证明 结果编辑页面开了2h无果……

Day2 20:35上传一下

上传失败了,Day4 00:02再上传一下

\begin{array}{l}a^{p-1}\equiv 1\,\,\left( \text{mod}\,p \right) \,\,\left( p\text{为素数,}p\nmid a\text{不成立且}a>0 \right)\\\text{记}A=\left\{ a,2a,3a,\cdots ,\left( p-1 \right) a \right\} ,B=\left\{ 1,2,3\cdots ,p-1 \right\}\\A=B\,\,\left( \text{mod}\,p \right) \\ \text{对于}\forall a\in A,\text{存在唯一}b\in B\text{且}a\equiv b\,\,\left( \text{mod}\,p \right) \\\text{如果}a_1,a_2\in A,a_1\equiv a_2\,\,\left( \text{mod}\,p \right) \,\,,\,\,\text{则上式不成立}\\\text{记}a_1=i\times a,a_2=j\times a\\\text{则有}i\times a\,\,\equiv \,\,j\times a\,\,\left( \text{mod}\,p \right) \,\,\left( 0<i,j<p \right) \\\therefore \left( i-j \right) \times a\equiv 0\,\,\left( \text{mod}\,p \right) \\\therefore \left( i-j \right) \equiv 0\,\,\left( \text{mod}\,p \right) \\\therefore i=j\\\because A=B\,\,\left( \text{mod}\,p \right) \\a\times 2a\times 3a\times \cdots \times \left( p-1 \right) a\equiv 1\times 2\times \cdots \times \left( p-1 \right) \,\,\left( \text{mod}\,p \right) \\a^{\left( p-1 \right)}\times \left( p-1 \right) !\equiv \left( p-1 \right) !\,\,\left( \text{mod}\,p \right) \\a^{p-1}\equiv 1\,\,\left( \text{mod}\,p \right) \end{array}

下面是二次探测的证明……? 主要是用在Miller-Rabin上吧……

\begin{array}{l}x^2\equiv 1\,\,\left( \text{mod}\,p \right) \,\,\left( p\text{为素数,}x\in \mathbb{Z} \right)\\x^2-1\equiv 0\,\,\left( \text{mod}\,p \right)\\\left( x+1 \right) \left( x-1 \right) \equiv 0\,\,\left( \text{mod}\,p \right)\\\left( x-1 \right) \equiv 0\text{或}\left( x+1 \right) \equiv 0\,\,\left( \text{mod}\,p \right)\\p=2\text{显然成立}\\p>2\text{时,}\\\left( x+1 \right) \equiv 0\,\,\text{或}\left( x-1 \right) \equiv 0\,\,\left( \text{mod}\,p \right)\\x\equiv \pm 1\,\,\left( \text{mod}\,p \right) \end{array}

接下来是Miller-Rabin,写的时候用费马小定理居然没有判gcd然后好长时间才查出来     真可怕

就放个板子 具体原理上面证完了。

不是很难,也就几行.


2018-3-22 update

遇到一个有趣的式子……

F\left( a+b \right) =F\left( a+1 \right) \times F\left( b \right) +F\left( a \right) \times F\left( b-1 \right)

还有就是

\begin{array}{l} \text{gcd}\left( F\left( a \right) ,F\left( b \right) \right) \\ =\,\,\text{gcd}\left( F\left( a-b+b \right) ,F\left( b \right) \right) \\ =\,\,\text{gcd}\left( F\left( a-b \right) \times F\left( b-1 \right) ,F\left( b \right) \right) \end{array}

然后可以化为

\text{gcd}\left( F\left( a-b \right) ,F\left( b \right) \right) \ =\ F\left( \text{gcd}\left( a,b \right) \right)


\begin{array}{l} \phi \left( x \right) =\left( a_1-1 \right) a_{1}^{p_1-1}\cdot \left( a_2-1 \right) a_{2}^{p_2-1}\cdots \left( a_n-1 \right) a_{n}^{p_n-1} \\ \text{原理:\ 当}x=p^n\text{时\ ,\ }\phi \left( x \right) =x-x/p=p^n-p^{n-1}=\left( p-1 \right) p^{n-1}\ \text{而且}\phi \left( x \right) \text{是积性函数} \end{array}


线性筛的证明

\gcd(n,m)=1 \Rightarrow \gcd(n+m,m)=1

n,m 不互质时,

b=\gcd(n,m) \;\; (b \ne 1) 则有

\begin{cases} n+m=k_2b\\ m=k_1b \end{cases} \;\;\;(k_1,k_2 \in \mathbb{Z})

\Rightarrow k_1b+n=k_2b

\Rightarrow n=(k_2-k_1)b

\Rightarrow \gcd(n,m)=b

这与\gcd(n,m)=1矛盾。

所以我们有了\varphi(p \times i)=p \times \varphi(i)