夢に僕らで帆を張って
来るべき日のために夜を超え

分类 算法 下的文章

October 24, 2019

自适应辛普森法

自适应辛普森法一、定积分定积分是积分的一种,是函数$f(x)$在区间$[a,b]$上积分和的极限定积分的几何意义是函数的曲线上$x$的一段区间与$x$轴围成的曲边梯形的带符号面积表示为$$\int_a^b f(x)\mathrm{d}x$$由定积分的定义,若函数$f(x)$在区间$[a,b]$上可积分,则有$n$等分的特殊分法$$\lim_{n \rightarrow +\infty} \s...
September 26, 2019

素数判断

素数判断一、素数的定义质数(prime number)又称素数,有无限个。质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。注意 $1$ 不是素数也不是合数。二、判断一个数是否为素数由定义可得,一个数 $n$ 为素数当且仅当它只含因数 $1$ 和它本身。于是可从 $2$ 枚举到 $n-1$ 判断其是否为 $n$ 的因数。inline bool isPrime(int x){ ...
September 26, 2019

卢卡斯定理

卢卡斯定理一、卢卡斯(Lucas)定理求$$C_n^m \ (\bmod \ p)$$1.定理$$ \begin{aligned} & a=a_kp^k+a_{k-1}p^{k-1}+\dots+a_1p+a_0 \\ & b=b_kp^k+b_{k-1}p^{k-1}+\dots+b_1p+b_0 \end{aligned} $$其中 $0 \le a_i,b_i \le ...
September 26, 2019

乘法逆元

乘法逆元一、逆元的定义若 $a \cdot x \equiv 1 \ (\bmod \ p)$ 且 $(a,p)=1$ ,则称 $a$ 关于模 $p$ 的乘法逆元为 $x$ ,记为 $a^{-1}$ 。二、逆元的求法1.费马(Fermat)小定理若 $p$ 为素数,且 $(a,p)=1$ ,则有 $a^{p-1} \equiv 1 \ (\bmod \ p)$ 。由费马小定理 $$a \cd...
September 26, 2019

欧拉定理&费马小定理&扩展欧拉定理

欧拉定理 & 费马小定理一、欧拉(Euler)定理1.定理若 $(a,m)=1$ ,则$$a^{\varphi(m)} \equiv 1 \ (\bmod \ m)$$ 其中 $\varphi(m)$ 为欧拉函数,定义为小于或等于 $m$ 的正整数中与 $m$ 互质的数的数目。2.证明:记模 $m$ 意义下的缩系(小于 $m$ 且与 $m$ 互素的正整数集合)$$R=\{x_1,x_2,\d...
September 26, 2019

欧几里得算法&扩展欧几里得算法

欧几里得算法一、欧几里得(Euclid)算法又称辗转相除法,用于求两数最大公约数。$$(a,b)=(b,a\%b)$$代码:int gcd(int a,int b){ return b?gcd(b,a%b):a; }二、扩展欧几里得(Euclid)算法用于求解方程 $$ax+by=(a,b)$$ 的所有整数解 $(x,y)$ 。考虑 $$(a,b)=(b,a\%b)$$$\becau...
September 26, 2019

中国剩余定理&扩展中国剩余定理

中国剩余定理一、中国剩余定理(CRT)求解同余方程组$$ \left\{ \begin{aligned} & x \equiv a_1 \ (\bmod \ m_1) \\ & x \equiv a_2 \ (\bmod \ m_2) \\ & \dots \\ & x \equiv a_n \ (\bmod \ m_n...
September 26, 2019

0/1分数规划

0/1分数规划一、分数规划给出若干二元组 $(v_i,c_i)$ ,要求从中选出一些,使得 $\frac{\sum v_i}{\sum c_i}$ 最大(最小)。二、解法先考虑最大,最小同理。1、二分法假设问题的最优解为 $ans$ ,则有$$\frac{\sum v_i}{\sum c_i} \le ans$$移项$$\sum v_i \le ans \cdot \sum c_i$$$$\...