筛法 - Sieve

Changelog Update 2021.10.03 增加PN筛 包含有: 线性筛,杜教筛,Min25筛,PN筛,州阁筛 本篇主要用于入门数论中的一些简单的筛法 虽然不是特别全面,但是后面会一步步完善的。 注意:不会对用到的数论函数解释,默认读者对数论有基本认知。 线性筛 从名字也可以看出,这种筛法为线性复杂度。 我们主要用它来得到某个积性函数函数值的表,(在线性的时间复杂度内得到)。 线性筛的基本思路,对于某个合数$n$,若它的最小质因子为$p$: 如果$(p,\frac{n}{p})\not = 1$,考虑函数本身,主要看质因子指数对函数值的影响。 如果$(p, \frac{n}{p})=1$,由积性函数的性质$f(n)=f(\frac{n}{p})f(p)$。 质数筛(顺便记录最小素因子) 按照合数的定义就知道了。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 int lpf[LIM]; vector<int> sieve() { vector<int> pr; for (int i = 2; i < LIM; i++) { if (lpf[i] == 0) { lpf[i] = i, pr.push_back(i); } for (const int &p : pr) { ll j = p * 1LL * i; if (j >= LIM) break; lpf[j] = p; if (i % p == 0) break; } } return pr; } 欧拉函数筛 设$(n,m)=d$,则有...

七月 28, 2021 · Kenshin2438

孙子剩余定理 - CRT/exCRT

之前介绍Lucas定理时,内容涉及到了中国剩余定理,以及欧拉定理。 后者应该是广为人知的定理(之后也会写拓展欧拉定理的吧),然而前者的名气似乎远有不如。 本篇以证明为主,(不喜欢证明的可以关了)当然也会遵循传统给出板子。 孙子剩余定理 设$m_1,m_2,\dots,m_k$为$k$个两两互素的正整数,$m=\prod{m_i}$。 令$m=m_iM_i$,则同余方程组 $$ \begin{cases} x &\equiv & b_1 \pmod{m_1} \newline x &\equiv & b_2 \pmod{m_2} \newline & \vdots & \newline x &\equiv & b_k \pmod{m_k} \end{cases} $$ 有唯一解 $$x\equiv {\sum_{i=1}^{k}{b_iM_iM_i^{-1}}}\pmod{m},M_iM_i^{-1}\equiv1\pmod{m_i}$$ 我们从基础解和基础解系的角度出发,构造这样一组基础解: $$ \begin{cases} x_1 & \equiv & 1 \pmod{m_1} \quad \newline x_1 & \equiv & 0 \pmod{m_2} \quad \newline & \vdots & \newline x_1 & \equiv & 0 \pmod{m_k} \quad \end{cases} \quad \dots \quad \begin{cases} x_k & \equiv & 0 \pmod{m_1} \quad \newline x_k & \equiv & 0 \pmod{m_2} \quad \newline & \vdots & \newline x_k & \equiv & 1 \pmod{m_k} \quad \end{cases} $$...

七月 25, 2021 · Kenshin2438

组合数取模 - Lucas/exLucas

Changelog Update at 2022.1.19 修正FastMod代码来源。 证明和代码分开,可以根据自己的需要跳转。 Lucas定理 $${n \choose m} \mod p = {\lfloor \frac{n}{p} \rfloor \choose \lfloor \frac{m}{p} \rfloor} {\langle n \rangle _p \choose \langle m \rangle _p} \mod p$$ 上式当$p$为素数时成立。 此时,若$p$为一个较小的素数,而$n,m$为一个较大的数(指不能直接通过预处理阶乘及其逆元的大数,比如$1e18$),那么我们就可以递归地求解该结果。 1 2 3 4 5 inline ll func(ll n, ll m, ll p, ll res = 1LL) { if (n < m) return 0; while (m) res = res * C(n % p, m % p) % p, n /= p, m /= p; return res; } 根据上述代码,我们只要预处理出$p$以内的阶乘及其逆元即可,时间复杂度$O(p+\log{m})$。...

七月 24, 2021 · Kenshin2438

素性检验 - Miller-Rabin Test

由费马小定理可以知道,如果$p$是一个素数,且$(x, p)=1$,我们可以得到: $$ \begin{aligned} x^{p-1} \equiv 1 \pmod{p} \end{aligned} $$ 那么反之,如果有$x$满足$\forall a>1,(a,x)=1,s.t. a^x \equiv 1 \pmod{x}$,这样的$x$一定是素数吗? 很可惜的是,上述逆定理并不成立。 例如 561=3 * 17 * 11, $$\forall a>1,(a,561)=1, s.t.a^{560}\equiv1\pmod{561}$$ 卡米歇尔数 $n$是卡米歇尔数的充分必要条件是: $n$无平方因子 $n$的每一个素因子$p$,有$p-1\mid n-1$ $n$是奇数且至少有三个不同的素因子 卡米歇尔数就是证伪上述逆定理的合数,即对任意$a>1,(a,n)=1$,都有$a^{n-1}\equiv1\pmod{n}$成立。 我们的目的是证伪,所以此处只证明充分性,至于必要性,读者自证不难。 设$n=\prod_{i=1}^{k}{p_i}$是一个米歇尔数,其中$p_i$是互不相同的奇素数。 对于任意$a>1,(a,n)=1$,则有$(a,p_i)=1$,由费马小定理知道 $$a^{p_i-1}\equiv 1 \pmod{p_i}$$ 由于$p_i-1\mid n-1$,可以得到 $$a^{n-1}\equiv 1 \pmod{p_i}$$ 所以$\forall a > 1, (a,n)=1$: $$a^{n-1}\equiv 1 \pmod{n}$$ 虽然费马小定理的逆定理不成立,但人们发现,如果增加条件,可以得到类似的结果。 Miller Rabin Algorithm 由费马小定理可知,如果$p$是素数,$\forall a\in Z_p^*,a^{p-1}\equiv1\pmod{p}$ 如果$p$为奇素数,那么我们可以得到$p-1$是一个偶数,则$p-1=k2^t,\textrm{k is odd}$ 据此,我们再看看费马小定理: $$ \begin{aligned} \because \quad & a^{p-1}=a^{k2^t}\equiv1\pmod{p} \newline \therefore \quad & a^{k2^t}-1\equiv0\pmod{p} \newline \therefore \quad & (a^{k}-1)\prod_{i=0}^{t-1}{(a^{k2^i}+1)}\equiv0\pmod{p} \newline \end{aligned} $$...

七月 4, 2021 · Kenshin2438

三次剩余 - Peralta Method Extension

Changelog update at 2022/06/10: 更新代码,并且新增范例(51Nod-1039),用于展示如何求得所有解。 LiBreOJ #175. 模立方根 题目链接 题目描述 $T$组输入,每组给出$a,p$,求同余方程$x^3 \equiv a \pmod{p}$的任一可行解,若无解则返回0。 数据范围 $T=10^5$,$p$为奇素数,$p<2^{30},a \in \mathbb{F}_p\setminus \{0\}$ 分析 题目显然是让我们求,若$a$在$p$的3次剩余系中,求出原数。 设$k\mid p-1,p-1=kq$,则$a$是模奇素数$p$的一个$k$次剩余的充分必要条件 $$a^q\equiv 1\pmod{p}$$ $\textrm{Proof:}$ 必要性:若$a$是$p$的一个$k$次剩余,则存在整数$x$,$(x,p)=1$,满足$x^k\equiv a \pmod{p}$,则$a^q \equiv x^{kq}=x^{p-1} \equiv 1 \pmod{p}$。 充分性:若$a^q\equiv 1\pmod{p}$,$g$是$p$的一个原根,则有$q,ind_{g}a\equiv 0 \pmod{p-1}$,即有$ind_{g}a\equiv0\pmod{\frac{p-1}{q}}$,得到$k\mid ind_ga$,即$a$是模$p$的一个$k$次剩余。 对素数形式的分析 $p$为$3n+2$形式的素数: 由费马小定理:$a^{p}\equiv a\pmod{p}$,即$a^{3n+2}\equiv a\pmod{p}$;同时也有$a^{p-1}\equiv 1\pmod{p}$,即$a^{3n+1}\equiv 1\pmod{p}$。两者相乘得到${(a^{2n+1})}^{3} \equiv a \pmod{p}$。 $p$为$3n+1$形式的素数时,解的存在性上面已经讨论了。若有解,我们虽然没有上述那么漂亮的解的形式,但这里有一个绝妙的算法可以解决该问题。 Peralta Method Extension The Peralta method is a fast way of computing square roots for a prime of form $p=2^eq+1$ $(q \not\equiv0\mod 2)$ for large $e$....

七月 2, 2021 · Kenshin2438

斯特林公式 - Stirling's approximation

$$n! \thickapprox \sqrt{2 \pi n} \left ( \frac{n}{e} \right )^{n}$$ 上次写题用到了斯特林公式,然后就被老师“喷”了…… 有一说一,活该被喷,虽然斯特林公式我一直在用,但是从来没有证过。为了以后大胆地用斯特林公式,这里简单写一个证明。 简要证明 这是一个很好的对阶乘的渐进估计,事实上,就算是对广义阶乘函数($\Gamma$)也很管用。 $$\textrm{Gamma Function: }\Gamma{(x)} = \int_{0}^{\infty} t^{x-1}e^{-t} \mathrm{d} t$$ 为了更好地研究阶乘函数,我们将其写成如下形式: $$x! = \Gamma (x+1) = \int_{0}^{\infty} {t^{x}e^{-t}} \mathrm{d} t = \int_{0}^{\infty} {e^{x \ln t - t}} \mathrm{d} t$$ 我们换一下元, $t = (s+1)x$ , $$ \begin{aligned} x! & = \int_{-1}^{\infty} {e^{x \ln(s+1) + x \ln x - x(s+1)}} x \ \mathrm{d} s \newline & = \frac{x^{x+1}}{e^{x}} \int_{-1}^{\infty} {e^{x\left ( \ln(s+1) - s\right )}} \ \mathrm{d} s \newline & = \frac{x^{x+1}}{e^{x}} \int_{-1}^{\infty} {e^{x\left ( -s + \sum_{n=1}^{\infty}{\frac{(-1)^{n-1}}{n} s^{n}} \right )}} \ \mathrm{d} s \newline & \thickapprox \frac{x^{x+1}}{e^{x}} \int_{-\infty}^{+\infty} {e^{-x \frac{s^2}{2}}} \ \mathrm{d} s \newline & = \frac{x^{x+1}}{e^{x}} \sqrt{\frac{2}{x}} \int_{-\infty}^{+\infty} {e^{-u^2}} \ \mathrm{d} u \newline & = \frac{x^{x}}{e^{x}} \sqrt{2 \pi x} \end{aligned} $$...

六月 3, 2021 · Kenshin2438

已知多边形的各边长,求其最大面积

我们要解决的问题: 边长的数值满足什么条件时,能构成一个多边形? 取到最大面积的情况下,该多边形有何特征? 最大面积的表达式是什么? 代码实现。 当然,到你看到这句话为止,这个问题我还没解决 2333 Q1、构成多边形的边的条件 我们从三角形出发。任意两边之和大于第三边是构成三角形的三边的充要条件。 猜测:任意一条边小于其它各边的和是构成该多边形的充要条件。 太显了(QAQ 不会证充分,但感觉是对的) Q2、最大面积下,多边形的特征 我们从三角形出发……三角形有个der的最大面积 (已知三边的三角形虽然不存在最大面积一说,但总能给我们一点启示 比如海伦公式、外接圆……) 首先,很显然,凸 > 凹。 依旧,我们从四边形出发。我们令四边形ABCD的四边分别为 $a$, $b$ ,$c$, $d$, 将其拆分为两个三角形再求面积。 不妨连接BD,令 $A = \alpha, C = \beta$, 则有 $$S_{ABD} = \frac{ad\sin\alpha}{2}, S_{CBD} = \frac{bc\sin\beta}{2}$$ 则 $$S_{ABCD} = S_{ABD}+S_{CBD}= \frac{ad\sin\alpha + bc\sin\beta}{2} $$ 由余弦定理知 $$BD^2 = a^2+d^2-2ad\cos\alpha = b^2+c^2-2bc\cos\beta $$ 得到 $$(a^2+d^2)-(b^2+c^2) = 2ad\cos\alpha + 2bc\cos\beta $$ 稍加计算得到 $$ S_{ABCD}=\sqrt{(s-a)(s-b)(s-c)(s-d)-abcd\cos^2(\frac{\alpha+\beta}{2})}$$ $$其中, s = \frac{a+b+c+d}{2} $$ 也就是著名的 布雷施特奈德公式 。...

三月 19, 2021 · Kenshin2438