数论基础2

数论基础2"/>

数论基础2

文章太长，前一部分点这里。

排列组合

这部分内容也许不属于数论，但经常会和数论放到一起考。

定义

排列： A n m A_n^m Anm​ 为从 n n n 个物品中拿 m m m 个物品出来排列的方案数。有些旧教材也会写成 P n m P_n^m Pnm​。
　　　 A n m = P n m = n ! ( n − m ) ! A_n^m=P_n^m=\dfrac{n!}{(n-m)!} Anm​=Pnm​=(n−m)!n!​
组合： C n m C_n^m Cnm​ 为从 n n n 个物品中拿 m m m 个物品出来组合的方案数。也可以写成 ( n m ) \dbinom nm (mn​)
　　　 C n m = ( n m ) = A n m m ! = n ! m ! ( n − m ) ! C_n^m=\dbinom nm=\dfrac{A_n^m}{m!}=\dfrac{n!}{m!(n-m)!} Cnm​=(mn​)=m!Anm​​=m!(n−m)!n!​

性质

1. C n 0 = C n n = 1 1.\quad C_n^0=C_n^n=1 1.Cn0​=Cnn​=1
2. C n k = C n n − k 2.\quad C_n^k=C_n^{n-k} 2.Cnk​=Cnn−k​
　　证明： C n n − k = n ! ( n − k ) ! ( n − ( n − k ) ) ! = n ! k ! ( n − k ) ! = C n k \begin{aligned} C_n^{n-k}&=\dfrac{n!}{(n-k)!(n-(n-k))!}=\dfrac{n!}{k!(n-k)!}=C_n^k\end{aligned} Cnn−k​​=(n−k)!(n−(n−k))!n!​=k!(n−k)!n!​=Cnk​​
3. C n + 1 k + 1 = C n k + C n k + 1 3.\quad C_{n+1}^{k+1}=C_n^k+C_n^{k+1} 3.Cn+1k+1​=Cnk​+Cnk+1​
　　证明： k k k 个不同的数中取 n n n 个，第 k k k 个数如果取的话有 C n − 1 k − 1 C_{n−1}^{k−1} Cn−1k−1​ 种取法，如果不取则有 C n k − 1 C_n^{k−1} Cnk−1​ 种。
4. C m + r + 1 r = ∑ i = 0 r C m + i i 4.\quad C_{m+r+1}^r=\sum\limits_{i=0}^r C_{m+i}^i 4.Cm+r+1r​=i=0∑r​Cm+ii​
　　证明：根据组合数递推公式，有：
　　　　　 ∑ i = 0 r C m + i i = C m 0 + C m + 1 1 + C m + 2 2 + ⋯ + C m + r r = C m 1 + C m + 1 1 + C m + 2 2 + . . . + C m + r r = C m + 2 1 + C m + 2 2 + . . . + C m + r r … = C m + r + 1 r \begin{aligned}\sum\limits_{i=0}^r C_{m+i}^i&=C_m^0+C_{m+1}^1+C_{m+2}^2+\dots+C_{m+r}^r\\ &=C_m^1+C_{m+1}^1+C_{m+2}^2+...+C_{m+r}^r\\ &=C_{m+2}^1+C_{m+2}^2+...+C_{m+r}^r\\ &\dots\\ &=C_{m+r+1}^r\end{aligned} i=0∑r​Cm+ii​​=Cm0​+Cm+11​+Cm+22​+⋯+Cm+rr​=Cm1​+Cm+11​+Cm+22​+...+Cm+rr​=Cm+21​+Cm+22​+...+Cm+rr​…=Cm+r+1r​​
5. C m n × C n r = C m r × C m − r n − r 5. \quad C_m^n\times C_n^r=C_m^r\times C_{m-r}^{n-r} 5.Cmn​×Cnr​=Cmr​×Cm−rn−r​
　　证明：代入定义式即可。
　　　　　 C m n × C n r = m ! n ! ( m − n ) ! × n ! r ! ( n − r ) ! = m ! r ! ( m − r ) ! × ( m − r ) ! ( m − n ) ! ( n − r ) ! = C m r × C m − r n − r \begin{aligned}C_m^n\times C_n^r&=\frac{m!}{n!(m-n)!}\times\frac{n!}{r!(n-r)!}\\ &=\frac{m!}{r!(m-r)!}\times \frac{(m-r)!}{(m-n)!(n-r)!}\\ &=C_m^r\times C_{m-r}^{n-r}\end{aligned} Cmn​×Cnr​​=n!(m−n)!m!​×r!(n−r)!n!​=r!(m−r)!m!​×(m−n)!(n−r)!(m−r)!​=Cmr​×Cm−rn−r​​
6. ( a + b ) n = ∑ r = 0 n C n r a n n − r b r 6. \quad (a+b)^n=\sum\limits_{r=0}^nC_n^ra_n^{n-r}b^r 6.(a+b)n=r=0∑n​Cnr​ann−r​br
　　证明：百度百科
7. n × C m n = m × C m − 1 n − 1 7.\quad n\times C_m^n=m\times C_{m-1}^{n-1} 7.n×Cmn​=m×Cm−1n−1​
　　证明：代入定义式即可。
　　　　　 n × C m n = n × m ! n ! ( m − n ) ! = m ! ( n − 1 ) ! ( m − n ) ! = m × ( m − 1 ) ! ( n − 1 ) ! ( m − n ) ! = m × C m − 1 n − 1 \begin{aligned}n\times C_m^n&=n\times \frac{m!}{n!(m-n)!}\\ &=\frac{m!}{(n-1)!(m-n)!}\\ &=m\times \frac{(m-1)!}{(n-1)!(m-n)!}\\ &=m\times C_{m-1}^{n-1}\end{aligned} n×Cmn​​=n×n!(m−n)!m!​=(n−1)!(m−n)!m!​=m×(n−1)!(m−n)!(m−1)!​=m×Cm−1n−1​​

组合数取模

公式

可不可以直接套用公式呢？答案是肯定的。

逆元

很抱歉，由于公式中有除法运算，因此需要求逆元，而模 p p p 意义下的逆元并不一定存在，因此这种方法仅仅使用于 p p p 为质数的情况下。
根据通项公式 C n m = n ! m ! ( n − m ) ! C_n^m=\dfrac{n!}{m!(n-m)!} Cnm​=m!(n−m)!n!​，可以发现，只需要预处理出阶乘的逆元和阶乘即可。

#define C(n,m) (((fac[n]*fac_inv[m])%mod*fac_inv[(n)-(m)])%mod)

卢卡斯定理

结论： C n m ≡ C ⌊ n p ⌋ ⌊ m p ⌋ × C n mod  p m mod  p ( m o d p ) \begin{aligned}C_n^m≡ C_{\lfloor {n\over p}\rfloor}^{\lfloor {m\over p}\rfloor}\times C_{n\ \text{mod}\ p}^{m\ \text{mod}\ p}\pmod p\end{aligned} Cnm​≡C⌊pn​⌋⌊pm​⌋​×Cn mod pm mod p​(modp)​
证明：设 a = ⌊ n p ⌋ , b = n mod  p , c = ⌊ m p ⌋ , d = m mod  p a=\Big\lfloor\dfrac{n}{p}\Big\rfloor,b=n\ \text{mod}\ p,c=\Big\lfloor\dfrac mp\Big\rfloor,d=m\ \text{mod}\ p a=⌊pn​⌋,b=n mod p,c=⌊pm​⌋,d=m mod p
　　　对于质数 p p p 由费马小定理得　 a p − 1 ≡ 1 ( m o d p ) a^{p-1}≡1\ \pmod p ap−1≡1 (modp)
　　　两边同时乘以 a a a，得　 a p ≡ a ( m o d p ) a^p≡a\ \pmod p ap≡a (modp)
　　　因此　 ( 1 + x ) p ≡ 1 + x ≡ 1 + x p ( m o d p ) (1+x)^p\equiv 1+x\equiv1+x^p\pmod p (1+x)p≡1+x≡1+xp(modp)
　　　有了这个性质就很开心了。为了书写方便，接下来所有同余运算皆在模 p p p 意义下进行。
　　　 ( 1 + x ) n ≡ ( 1 + x ) a ⋅ p ( 1 + x ) b ≡ ( 1 + x p ) a ( 1 + x ) b ≡ ∑ i = 0 k C a i x p i ∑ j = 0 k C b j x j \begin{aligned}(1+x)^n&≡(1+x)^{a\cdot p}(1+x)^{b}\\ &≡(1+x^p)^{a}(1+x)^{b}\\ &≡\sum\limits _{i=0}^kC_{a}^ix^{pi}\sum\limits_{j=0}^kC_{b}^jx^j\end{aligned} (1+x)n​≡(1+x)a⋅p(1+x)b≡(1+xp)a(1+x)b≡i=0∑k​Cai​xpij=0∑k​Cbj​xj​
　　　观察等式两边的 x m x^m xm 的系数，可得：
　　　等式左边 x m x^m xm 的系数，可以发现：
　　　 C n m ≡ C a i C b j ( p i + j = m , j < p ) ≡ C a c C b d ≡ C ⌊ n p ⌋ ⌊ m p ⌋ C n mod  p m mod  p \begin{aligned}C_n^m&≡C_{a}^iC_{b}^j\quad(pi+j=m,j<p)\\ &≡C^{c}_{a}C_{b}^{d}\\ &≡C^{\lfloor \frac mp\rfloor}_{\lfloor \frac np\rfloor}C_{n\ \text{mod}\ p}^{m\ \text{mod}\ p}\end{aligned} Cnm​​≡Cai​Cbj​(pi+j=m,j<p)≡Cac​Cbd​≡C⌊pn​⌋⌊pm​⌋​Cn mod pm mod p​​

组合数奇偶

如果让你计算 C n m mod  2 C_n^m\ \text{mod}\ 2 Cnm​ mod 2 你会？

1. 计算时间复杂度 O ( n ) O(n) O(n)
2. 卢卡斯定理时间复杂度 O ( l o g 2 n ) O(log_2n) O(log2​n)
   如果我告诉你可以做到 O ( 1 ) O(1) O(1)，你会有什么反应？
   结论：设有 x x x 满足 C n m ≡ x ( m o d 2 ) C_n^m≡x\pmod 2 Cnm​≡x(mod2)，则有
   x = { 0 ( x a n d m = m ) 1 ( x a n d m ≠ m ) x=\begin{cases}0&(x&and&m=m)\\1&(x&and&m\not =m)\end{cases} x={01​(x(x​andand​m=m)m=m)​

证明：（坑）

质数

定义：若 x x x 只含有 1 1 1 和 x x x 两个因数，则 x x x 为质数，也叫做素数。

判断质数

暴力

滚滚滚，谁用你讲这个。这不是重点，重点是后面的。
那就直接上代码啦！

bool prime(int x){if(x==1) return false;const int l=x-1;for(int i=2;i<=l;i++)if(!(x%i))return false;return true;
}

时间复杂度 O ( n ) O(n) O(n)

初步优化

可以发现，一个数的因数总是成对出现(包括自身和自身)
而其中的一个因数总是小于 x \sqrt x x ​ 因此，枚举时只需要枚举到 x \sqrt x x ​ 就好了。

bool prime(int x){if(x==1) return false;const int l=floor(sqrt(x)+0.5);for(int i=2;i<=l;i++)if(!(x%i))return false;return true;
}

时间复杂度 O ( n ) O(\sqrt n) O(n ​)

进一步优化

什么，还可以优化？我怎么不知道？
你当然不知道。因为这里用到了一个很神仙的结论。
结论：大于等于 5 5 5 的质数一定和 6 6 6 的倍数相邻。
证明：令 x ⩾ 1 x\geqslant1 x⩾1 ，将大于等于 5 5 5 的自然数表示如下：
6 x − 1 , 6 x , 6 x + 1 , 6 x + 2 , 6 x + 3 , 6 x + 4 , 6 x + 5 , … 6x-1,6x,6x+1,6x+2,6x+3,6x+4,6x+5,\dots 6x−1,6x,6x+1,6x+2,6x+3,6x+4,6x+5,…
其中， 6 x − 1 6x-1 6x−1， 6 x + 1 6x+1 6x+1 和 6 x + 5 6x+5 6x+5 与 6 x 6x 6x 相邻.
6 x + 2 = 2 ( 3 x + 1 ) 6x+2=2(3x+1) 6x+2=2(3x+1)，合数。
6 x + 3 = 3 ( 2 x + 1 ) 6x+3=3(2x+1) 6x+3=3(2x+1)，合数。
6 x + 4 = 2 ( 3 x + 2 ) 6x+4=2(3x+2) 6x+4=2(3x+2)，合数。
因此，质数必然形如 6 x − 1 6x-1 6x−1 或 6 x + 1 6x+1 6x+1
这样就可以很好地降低时间复杂度了。

bool primes(int x){if(x==1) return false;if(x==2||x==3)return true;if(x%6!=1&&x%6!=5)return false;const int l=floor(sqrt(x)+0.5);for(int i=2;i<=l;i++)if(!(x%i))return false;return true;
}

时间复杂度 O ( 1 ) ∼ O ( n ) O(1)\sim O(\sqrt n) O(1)∼O(n ​)

再优化

什么！还可以再优化！很肯定地告诉你是的。
是不是感觉自己的智商被侮辱了？
对于一个数 x x x，如果 x x x 可以整除一个合数，那么 x x x 一定可以整除 y y y 的任何一个质因数。
这样我们就只需要判断它是否能整除小于 x \sqrt x x ​ 的质数就可以了。
可我们又怎么得到质数？虽然我们不能直接得到质数，但是我们可以得到一些很有可能是质数的数。
根据上一小节的结论，可以发现质数必然靠近 6 6 6 的倍数。因此判断的时候，循环步长可以为 6 6 6。
代码：

bool prime( int x ){  if(x==1) return false;if(x==2||x==3)return true;if(x%6!=1&&x%6!=5)return false;int tmp=floor(sqrt(x)+0.5);for(int i=5;i<=tmp;i+=6)if(x%i==0||x%(i+2)==0)return false;return true;
}

时间复杂度： O ( 1 ) ∼ O ( n 6 ) O(1)\sim O(\frac{\sqrt n}6) O(1)∼O(6n ​​)

终极法则

为什么这一小节的标题中不含有“优化”二字了呢？因为我们又换算法了。

费马算法

回忆一下费马小定理。

---

若 ( a , p ) = 1 , p ∈ p r i m e (a,p)=1,p\in prime (a,p)=1,p∈prime ，则 a p − 1 ≡ 1 ( m o d p ) a^{p-1}≡1\pmod p ap−1≡1(modp)。

---

那么反过来看，对于一个正整数 p p p，如果存在一个正整数 a a a，满足 a p − 1 ≢ 1 ( m o d p ) a^{p-1}\not≡1\pmod p ap−1≡1(modp)，那么我们可以肯定 p p p 是合数，因为如果 p p p 是质数，则与费马小定理矛盾。

二次探测定理

费马定理是一个RP算法，即能在多项式时间内求出答案，但对于否定状态可以做肯定判断（即100%不是质数），但对于肯定状态却不一定能做出肯定判断（即不一定是质数），可是它的正确率实在太低了，因此需要更强的算法。
结论：若 p ∈ p r i m e p\in prime p∈prime，存在 x x x 满足 x < p , x ∈ N ∗ , x 2 ≡ 1 ( m o d p ) x<p,x\in N^*,x^2≡1\pmod p x<p,x∈N∗,x2≡1(modp)。
\quad\qquad 则有 x ≡ 1 ( m o d p ) x≡1\pmod p x≡1(modp) 或 x ≡ p − 1 ( m o d p ) x≡p-1\pmod p x≡p−1(modp)
证明： ∵ x 2 ≡ 1 ( m o d p ) \because x^2≡1\pmod p ∵x2≡1(modp)
∴ x 2 − 1 ≡ 0 ( m o d p ) \qquad\ \therefore x^2-1≡0\pmod p  ∴x2−1≡0(modp)
∴ ( x + 1 ) ( x − 1 ) ≡ 0 ( m o d p ) \qquad\ \therefore (x+1)(x-1)≡0\pmod p  ∴(x+1)(x−1)≡0(modp)
∴ x ≡ 1 ( m o d p ) 或  x ≡ p − 1 ( m o d p ) \qquad\ \therefore x≡1\pmod p\ 或\ x≡p-1\pmod p  ∴x≡1(modp) 或 x≡p−1(modp)
和费马定理合起来就是完整的Miller-Rabin算法了。
举个例子：当 p = 341 , a = 2 p=341,a=2 p=341,a=2 时，可以发现， a p − 1 ≡ 2 340 ≡ 1 ( m o d p ) a^{p-1}≡2^{340}≡1\pmod p ap−1≡2340≡1(modp)，通过了费马测试。
这种时候，Miller-Rabin算法并不是马上换一个 a a a，而是二次探测。发现 340 340 340 是个偶数，则令 u = 340 2 = 170 u=\frac{340}2=170 u=2340​=170，然后检测 a u ≡ 2 170 ≡ 1 ( m o d 341 ) a^u≡2^{170}≡1\pmod {341} au≡2170≡1(mod341)，发现满足二次探测定理，然后发现 170 170 170 还是个偶数，因此计算 a 85 ≡ 2 85 ≡ 34 ( m o d 341 ) a^{85}≡2^{85}≡34\pmod {341} a85≡285≡34(mod341)不满足二次探测定理，因此 341 341 341 不是质数。
我们的老祖宗告诉我们，若 p p p 通过一次Miller-Rabin算法，则 p p p 不是质数的概率降低到 1 4 \dfrac 14 41​。
这个概率还是很让人担忧，但是如果执行多次呢？执行 S S S 次算法后， p p p 不是质数的概率降低到了 1 4 S \dfrac 1{4^S} 4S1​。因此，我们可以不断地生成随机数来判断，只要判断几次就能把概率提高。
时间复杂度 O ( S l o g 2 n ) O(Slog_2n) O(Slog2​n)

取数方法

一般底数仍然是随机选取，但当待测数不太大时，选择测试底数就有一些技巧了。

测试数组	被测上限	例外
2 , 3 2,3 2,3	1373653 1373653 1373653
31 , 73 31,73 31,73	9080191 9080191 9080191
2 , 7 , 61 2,7,61 2,7,61	4759123141 4759123141 4759123141
2 , 13 , 23 , 1662803 2,13,23,1662803 2,13,23,1662803	1122004669633 1122004669633 1122004669633
2 , 3 , 5 , 7 , 11 , 13 , 17 2,3,5,7,11,13,17 2,3,5,7,11,13,17	341550071728320 341550071728320 341550071728320
2 , 3 , 7 , 61 , 24251 2,3,7,61,24251 2,3,7,61,24251	1 0 16 10^{16} 1016	46856248255981 46856248255981 46856248255981
时间复杂度为： O ( k log ⁡ 2 k ) O(k\log_2k) O(klog2​k)，其中k是测试组数。

筛法

这里只讨论筛质数，筛函数请移步到莫比乌斯反演。
如果我需要求出一定范围内的质数表，你会怎么做？
如果每次循环，并且判断某个数是否为质数当然可行，但没有用到线性计算的优势——在你计算某个答案的时候，前面的所有答案已经出来了。

Eratosthenes筛法

考虑换一种方法，每次把2的倍数的数全部从质数表中删去，然后再把把3的倍数的数全部从质数表中删去，以此类推，最后会得到完整的指数表。这就是最简单的 Eratosthenes 筛法。

void eratosthenes_sieve(int n){memset(vis,0,sizeof(vis));for(int i=2;i<=n;i++)for(int j=i*2;j<=n;j+=i)vis[j]=1;
}

这份代码尽管还可以优化，但已经非常快了。显而易见地，外层循环为 i i i 时，内层循环的次数是 ⌊ n i ⌋ − 1 < n i \lfloor\dfrac ni\rfloor-1<\dfrac ni ⌊in​⌋−1<in​，因此程序的时间复杂度为 O ( ∑ i = 2 n n i ) = O ( n ln ⁡ n ) O(\sum\limits^{n}_{i=2}\frac ni) =O(n\ln n) O(i=2∑n​in​)=O(nlnn)，为什么？
这是欧拉在1734年得到的结果 S = 1 + 1 2 + 1 3 + ⋯ + 1 n = ln ⁡ n + γ S=1+\frac 12+\frac 13+\dots+\frac 1n=\ln n+γ S=1+21​+31​+⋯+n1​=lnn+γ，他发现， γ = S − ln ⁡ n γ=S-\ln n γ=S−lnn 是一个定值，约等于 0.5772156649 0.5772156649 0.5772156649，这个定值也被称为欧拉常数，可惜的是目前人类对这个常数的了解还很少，甚至连它是个有理数还是无理数都不知道。
类似地，其实外层循环只需要到 n \sqrt n n ​ 就够了。并且内层循环从 i 2 i^2 i2 开始就好了。
为什么？因为能被 i × 2 i\times 2 i×2 筛掉的数在 2 2 2 那一次循环中就已经被筛掉了。

void eratosthenes_sieve(int n){memset(vis,0,sizeof(vis));int l=floor(sqrt(n)+0.5);for(int i=2;i<=l;i++)if(!vis[i])for(int j=i*i;j<=n;j+=i)vis[j]=1;
}

时间复杂度再一次降低。

欧拉筛法

欧拉筛法的优点不仅仅在于它可以证明时间复杂度是线性的，还在于可以同时出许多积性函数表。
先上代码

void euler_sieve(int n){memset(vis,false,sizeof(vis));//是否是质数 memset(prime,0,sizeof(prime));//质数表 for(int i=2;i<=n;i++) {if(!vis[i])prime[cnt++]=i;//找到素数for(int j=0;j<cnt&&i*prime[j]<=n;j++) {vis[i*prime[j]]=true;//筛掉合数 if(i%prime[j]==0)break;	//(*)}}
}

上面的(*)是关键，为什么i%prime[j]==0就可以退出了呢？
这里规定，每个合数必须被其最小的质因数的倍数筛掉。
因为 i ∗ p r i m e [ j + 1 ] i*prime[j+1] i∗prime[j+1] 已经被筛掉了。可又是为什么？
因为 i % p r i m e [ j ] = 0 i\%prime[j]=0 i%prime[j]=0，因此存在正整数 k k k 满足 i = p r i m e [ j ] ∗ k i=prime[j]*k i=prime[j]∗k。
后面将要筛掉的 i ∗ p r i m e [ j + 1 ] i*prime[j+1] i∗prime[j+1] 可表示成 p r i m e [ j ] ∗ k ∗ p r i m e [ j + 1 ] prime[j]*k*prime[j+1] prime[j]∗k∗prime[j+1]
而 p r i m e [ j ] < p r i m e [ j + 1 ] prime[j]<prime[j+1] prime[j]<prime[j+1] 。
故 p r i m e [ j + 1 ] prime[j+1] prime[j+1] 并不是 i ∗ p r i m e [ j + 1 ] i*prime[j+1] i∗prime[j+1] 的最小质因数，而它也必然将要被 p r i m e [ j ] prime[j] prime[j] 的倍数筛掉。因此每个数只会被筛掉一次，因此时间复杂度为完美的 O ( n ) O(n) O(n)