Posts

先给出全部公式： $$ \begin{aligned} & \sin^{2n}{x}=\frac{1}{2^{2n-1}}\left[ \sum_{k=0}^{n-1}{2n \choose k}(-1)^{n-k}\cos{2(n-k)x} + \frac{1}{2}{2n \choose n} \right] \newline & \sin^{2n+1}{x}=\frac{1}{2^{2n}}\sum_{k=0}^{n}{2n+1 \choose k}(-1)^{n-k}\sin{(2n-2k+1)x} \newline & \cos^{2n}{x}=\frac{1}{2^{2n-1}}\left[ \sum_{k=0}^{n-1}{2n \choose k}\cos{2(n-k)x}+\frac{1}{2}{2n \choose n} \right] \newline & \cos^{2n+1}{x}=\frac{1}{2^{2n}}\sum_{k=0}^{n}{2n+1 \choose k}\cos{(2n-2k+1)x} \newline \end{aligned} $$ 虽然看起来原本简单的式子被极大地复杂化了，但其实在很多命题中，它们起着十分不错的化简作用。 Proof 由欧拉恒等式$e^{ix}=\cos{x}+i\sin{x}$有 $$ \begin{cases} \sin x &=& \frac{e^{ix}-e^{-ix}}{2i} \newline \cos x &=& \frac{e^{ix}+e^{-ix}}{2} \end{cases} $$ 可以得到 $$ \begin{aligned} \sin^{2n}{x} & = \left(\frac{e^{ix}-e^{-ix}}{2i}\right)^{2n} \newline & = \frac{1}{(-1)^{n}2^{2n}}\sum_{k=0}^{2n}{2n \choose k}{(-1)^{2n-k}e^{ixk-ix(2n-k)}} \newline & = \frac{1}{2^{2n}}\sum_{k=0}^{2n}{2n \choose k}(-1)^{(n-k)}e^{i2(n-k)x} \newline & = \frac{1}{2^{2n}}{2n \choose n}+\frac{1}{2^{2n-1}}\sum_{k=0}^{n-1}{2n \choose k}(-1)^{n-k}\cos{2(n-k)x}\newline \newline \cos^{2n}{x} & = \left(\frac{e^{ix}+e^{-ix}}{2}\right)^{2n} \newline & = \frac{1}{2^{n}}\sum_{k=0}^{2n}{2n \choose k}{e^{i2(k-n)x}} \newline & = \frac{1}{2^{2n}}\left[\sum_{k=0}^{n-1}{2n \choose k}{e^{i2(k-n)x}}+\sum_{k=0}^{n-1}{2n \choose k}{e^{i2(n-k)x}}\right] + \frac{1}{2^{2n}}{2n \choose n} \newline & = \frac{1}{2^{2n}}{2n \choose n}+\frac{1}{2^{2n-1}}\sum_{k=0}^{n-1}{2n \choose k}{\cos2(n-k)x} \end{aligned} $$...

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$，则有...

之前介绍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} $$...

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})$。...

由费马小定理可以知道，如果$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} $$...

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$....

$$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} $$...

我们要解决的问题： 边长的数值满足什么条件时，能构成一个多边形？ 取到最大面积的情况下，该多边形有何特征？ 最大面积的表达式是什么？ 代码实现。 当然，到你看到这句话为止，这个问题我还没解决 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} $$ 也就是著名的 布雷施特奈德公式 。...