数论基础
质数
约数
同余
inline void prim(int limit) {//埃筛
vis[1] = 1;
for (int i = 2;i <= limit; ++i) {
if (!vis[i]) {
prims[++p_cnt] = i;
for (int j = i * i;j <= limit; j += i) vis[j] = 1;
}
}
}
inline void ola_prim(int limit) {//欧筛
vis[1] = 1;
for (int i = 2;i <= limit; ++i) {
if (!vis[i]) {
vis[i] = i;
prims[++p_cnt] = i;
}
for (int j = 1;j <= p_cnt; ++j) {
if (prims[j] > vis[i] || prims[j] > limit / i) break;
vis[i * prims[j]] = prims[j];
}
}
}
\[
gcd(a,b)=gcd(b,a\%b)
\]
数学归纳法可推广到一般。
描述:
如果任意整数\(a\)和\(b\)不都为\(0\),则\(gcd(a,b)\)是\(a\)与\(b\)的线性组合集\(\{ax+by:x,y\in Z\}\)中的最小正元素。
证明:
设\(s\)是线性组合集\(\{ax+by:x,y\in Z\}\)中的最小正元素,\(q=\lfloor a/s\rfloor\)。
所以必存在一组\(x,y\)使得\(ax+by=s\)。
所以\(a\%s=a-qs=a-q(ax+by)=a(1-qx)+b(-qy)\)
因此\(a\%s\)也是\(a\)与\(b\)的一个线性组合。
由于\(s\)是这个线性组合中最小正数,所以\(a\%s=0\)。即\(s|a\),同理,\(s|b\),所以\(gcd(a,b)\ge s\)。
因为\(gcd(a,b)|s\)和\(s>0\),所以\(gcd(a,b)\le s\)。
即\(gcd(a,b)=s\)。
得证。
加法原理:做一件事情,完成它有\(n\)类方式,第一类方式有\(m_1\)种方法,第二类方式有\(m_2\)种方法,…,第\(n\)类方式有\(m_n\)种方法,那么完成这件事情共有\(m_1+m_2+……+m_n\)种方法。
乘法原理:做一件事,完成它需要分成\(n\)个步骤,做第一步有\(m_1\)种不同的方法,做第二步有\(m_2\)种不同的方法,……,做第\(n\)步有\(m_n\)种不同的方法。那么完成这件事共有 \(m_1×m_2×m_3×…×m_n\)种不同的方法。
全排列:\(A_n^m=\frac{n!}{(n-m)!}=A_{n-1}^{m}+A_{n-1}^{m-1}*m\)
组合数:\(C_n^m=\frac{n!}{m!(n-m)!}=C_{n-1}^{m-1}+C_{n-1}^m\)
性质:
\[ (x+y)^n=C_n^0x^ny^0+C_n^1x^{n-1}y^1+...+C_n^{n-1}x^1y^{n-1}+C_n^nx^0y^n \]
可用数学归纳法证明。
交集相加减得并集。
\[
ans=1+\sum_{i=1}^nA[i]*(n-i)!
\]
\(A[i]\):当前位置往后比当前位置数小的个数,可用树状数组求。
有\(a\)个球,\(b\)个盒,求满足放置条件的方案数。
编号 | 球相同 | 盒相同 | 盒可为空 | 计算 |
---|---|---|---|---|
\(1\) | × | √ | × | \(s_2(a,b)\) |
\(2\) | × | √ | √ | \(\sum_{i=1}^{b}s_2(a,i)\) |
\(3\) | × | × | × | \(b!s_2(a,b)\) |
\(4\) | × | × | √ | \(b^a\) |
\(5\) | √ | √ | × | \(dp[n][m]\) |
\(6\) | √ | √ | √ | \(dp[n+m][m]\) |
\(7\) | √ | × | × | \(C_{a-1}^{b-1}\) |
\(8\) | √ | × | √ | \(C_{a+b-1}^{b-1}\) |
说明:
表中\(s_2\)指的是第二斯特林数。
递推式:\(s_2(n,m)=s_2(n-1,m-1)+s_2(n-1,m)*m\)。
同时,贝尔数\(Bell_n=\sum_{i=1}^{b}s_2(a,i)\)。
情况\(5\)和\(6\)的递推式:\(dp[n][m]= dp[n-m][m]+ dp[n-1][m-1]\)。
简要分析如下: