数论基础

一、基础概念（略）

质数

约数

同余

二、质数

A.质数筛法

暴力筛（略）

埃筛（(O(nloglogn))）

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;
		}
	}
}

欧筛（(O(n))）

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];
		}
	}
} 

三、约数与同余

A.欧几里得算法

[gcd(a,b)=gcd(b,a\%b) ]

数学归纳法可推广到一般。

B.裴蜀定理

描述：
如果任意整数(a)和(b)不都为(0)，则(gcd(a,b))是(a)与(b)的线性组合集({ax+by:x,yin Z})中的最小正元素。

证明：
设(s)是线性组合集({ax+by:x,yin Z})中的最小正元素，(q=lfloor a/s floor)。
所以必存在一组(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)。
得证。

C.扩展欧几里得算法

四、组合计数

A.加法和乘法原理

加法原理：做一件事情，完成它有(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)种不同的方法。

B.排列组合公式

全排列：(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)

性质：

• (sum_{i=0}^nC_n^i=2^n)（根据意义去思考）
• (sum_{k=0}^n(-1)^kC_n^k=0)
• (C_n^m=C_n^{n-m})
• (C_{n+m}^r=sum_{i=0}^rC_n^iC_m^{r-i})

C.二项式定理

[(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 ]

可用数学归纳法证明。

D.容斥原理

交集相加减得并集。

E.斯特林数

• 第一类斯特林数：(n)个不同元素构成(m)个圆排列的数目。
  (s_1(n,m)=s_1(n-1,m-1)+s_1(n-1,m)*(n-1))
• 第二类斯特林数：(n)个不同的元素拆分成(m)个集合的方案数。
  (s_2(n,m)=s_2(n-1,m-1)+s_2(n-1,m)*m)
• 贝尔数：集合划分的方案数。
  (B_n=sum_{i=1}^ns_2(n,i)=sum_{k=0}^nC_n^kB_k)

F.康托展开

[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])。

简要分析如下：

1. (n)个不同的元素拆分成(m)个集合的方案数，等同于第二斯特林数。
2. 允许出现空集，所以(sum)求和。
3. 容斥原理做，或者可以理解为因为盒子不同，所以直接乘上盒子的排列。
4. 最好理解：每个球有(b)种放法。
5. 这个问题等效成把一个数n拆成m个数，且先拆出的数不小于后拆出的数（避免重复情况）。如果这么拆：(x_1+x_2+x_3+...+x_m=n (x_i>=1))。当(x_1=1)时，后面的拆法表示成(dp[n-1,m-1])。当(x_1>=2)时，式子可以变成((x_1-1)+(x_2-1)+...+(x_m-1)=n-m)。所以后面的拆法表示成(dp[n-m,m])。所以得到递推式。
6. 在情况(5)下，每盒先放一个。
7. 插板问题。
8. 同插板问题。