Pollard’s Rho 较大整数因数分解

建议看一下网上找到的文章

如何分解

要分解 $n$ ,只需要找到一个 $d$ 使 $gcd(n,d)\neq 1$ ,然后分别分解 $d$ 和 $\frac{n}{d}$ 即可
但是这个 $d$ 十分难找,根据生日悖论(具体看pdf里的东西),我们随机找两个数 $x_i,x_j$
判断 $gcd(|x_i-x_j|,n)$ 是否为 $1$ ,然后进行继续选取或直接分解,碰中的几率会大很多
于是设 $f_i=f_{i-1}^2+c$ ,然后分别生成(伪)随机数来进行判定
但是程序中需要判断某个大整数是否为素数,这就需要用到 Miller-Rabin算法
发现这样生成 $f$ 可能会生成环,这会导致程序陷入死循环,此时需要跳出 继续阅读

Miller-Rabin 素数判定 与 较大数取模

米勒拉宾判定

LOJ – 质数判定
最近学了这个随机化的素数判定方法,终于学懂了(我之前学的肯定是假的
给一个建议:最好不要去Wikipedia – 米勒-拉宾素性检验上看
我随便讲一下,因为最近有点事多
首先对于一个数 $p$ ,如果它是素数,那么由于费马小定理:
$$ a^{p-1}\equiv 1\pmod{p}$$
看上去似乎只要枚举一些 $a$ 判断是否满足就行了,但实际上很容易被卡掉
这时候考虑引入其他的限制来进行进一步的判断
继续阅读

快速沃尔什变换备忘录

这真的仅仅是一个备忘录,没什么自己的东西
包含一些莫比乌斯变换的东西
我一开始就到 picks 的博客上去学果然是个错误的决定,表示学完之后云里雾里
然后又找了几个博客,还是不太明白,果然是因为我太渣了
然后到学长的博客上去看了一下,真是好明白多了
既然别人有写得很仔细的文章了,我就懒得写了,可以到底下链接去看,我只会写一些我学习时遇到的一点问题
继续阅读

自然数幂和

自然数幂和问题,是给定 $n, k$ ,求
$$ f_k(n)=\sum_{i=1}^{n}i^k $$
之前在伯努利数备忘录里面写了一点自然数幂和
后来又看到几个大爷在博客里面写了自然数幂和,所以又开一篇文章来引用一下其他的方法,我都只是简要提一下思路,具体方法在链接里

Miskcoo 的方法

以下思路与图片来自miskcoo 的博客
感觉思路新奇,明明看上去很简单,但是我怎么就想不到
首先考虑 $S_n=\sum_{i=1}^{n}i^2$ 应该怎样求解
1.png
继续阅读

莫比乌斯反演

一个小题

先讲一个同学出的题了解一下一种数论变换方式
给定 $n(n\leq 10^6)$ ,求
$$ \prod_{i=1}^{n}\prod_{j=1}^{n}\frac{lcm(i,j)}{gcd(i,j)} $$
虽然有 $\mathcal{O(n)}$ 的方法,但是这里不提了
考虑式子化简
$$\prod_{i=1}^{n}\prod_{j=1}^{n}\frac{lcm(i,j)}{gcd(i,j)}$$
$$ =\prod_{i=1}^{n}\prod_{j=1}^{n}\frac{i\cdot j}{gcd^2(i,j)}=\frac{\prod_{i=1}^{n}\prod_{j=1}^{n}i\cdot j}{\prod_{i=1}^{n}\prod_{j=1}^{n}gcd^2(i,j)} $$
上面很好处理,于是考虑下面怎么求
继续阅读

容斥原理备忘录

这个备忘录可能很短,因为我也不知道要写什么。。。

容斥的普遍公式

要计算几个集合并集的大小,我们要先将所有单个集合的大小计算出来,然后减去所有两个集合相交的部分,再加回所有三个集合相交的部分,再减去所有四个集合相交的部分,依此类推,一直计算到所有集合相交的部分。
最终得到公式:
$$ \left|\bigcup_{i=1}^n A_i\right| = \sum_{\emptyset\neq J\subseteq{1,2,\ldots,n}}(-1)^{|J|-1} \Biggl|\bigcap_{j\in J} A_j\Biggr| $$
公式其实不太好看,还是从文字来理解比较好
接下来随便看一个例子

错排数

错排数是保证任意一个数字不在原位置 ($a_i\neq i$)的排列数
记长度为 $n$ 的错排数为 $D_n$ ,则
$$D_n=n!\sum_{i=0}^{n}\frac{(-1)^i}{i!} $$
继续阅读

斯特林数备忘录

这个真的只是一个备忘录
而且基本上是从维基百科上 copy 的

第一类斯特林数

第一类 Stirling 数是有正负的,其绝对值是 $n$ 个元素的项目分作 $k$ 个环排列的方法数目。常用的表示方法有 $s(n,k)$
换个较生活化的说法,就是有 $n$ 个人分成 $k$ 组,每组内再按特定顺序围圈的分组方法的数目。例如 $s(4,2)=11$
继续阅读

伯努利数备忘录

本文有将近 50 个公式,谨慎观看

定义及推导

定义伯努利数为满足
$$ \frac{x}{e^x-1}=\sum_{n\geq 0} B_n\frac{x^n}{n!} $$
的有理数列
虽然已经得到了它的生成函数,但是发现仅凭这样一个多项式并不好推
于是考虑将其化简,对 $e^x$ 泰勒展开后
$$ \frac{x}{e^x-1} = \frac{x}{\sum_{i\geq 0}\frac{x^i}{i!}-1} $$
$$\frac{x}{e^x-1}=\frac{x}{\sum_{i\geq 1}\frac{x^i}{i!}}​$$
继续阅读

多项式的一些奇怪操作

之前讲了一些多项式常用的操作

多项式除法与取模

对于一个 $n$ 次多项式 $A(x)$ 和一个 $m$次多项式 $B(x)$. $m\leq n$ .
求 $Q(x),R(x)$ 使
$$ A(x)\equiv Q(x)* B(x)+R(x) $$
其中 $Q(x)$ 是一个 $n-m$ 次多项式,而 $R(x)$ 是一个小于 $m$ 次的多项式
可以在 $O(n\log n)$ 复杂度内求出,求解思路清奇,一般记结论就行了。
记 $A^{r(n)}(x)$ 表示一个次数小于等于 $n$ 的多项式 $A(x)$ 以 $x^n$ 为最高次项进行翻转得到的多项式
显然 $A^{r(n)}(x)=x^n*A(\frac{1}{x})$
继续阅读

多项式备忘录

最近学了多项式相关的一些东西,写一点备忘录,主要是公式和证明,可能每次只会写一点点。

导数

部分简单函数的导数

$$ (e^x)’ = e^x , (\ln x)’=\frac{1}{x} , (\sin x)’ = \cos x , (\cos x)’ = -\sin x $$

函数复合求导

$$ (f(x)+g(x))’ = f'(x) + g'(x) $$
$$ (f(x)g(x))’ = f'(x)g(x)+f(x)g'(x) $$
$$ (f(g(x)))’ = f'(g(x))g'(x) $$
上面这个比较重要,经常容易忘记多个函数复合,都要求导。
继续阅读