初等数论学习笔记

wdgm4 / 2023-05-20 / 原文

线性筛素数

直接上代码。

const int MAXN=100000008;
bool np[MAXN];
vector<int> prm,pre;
void gg(const int N=100000000){
	pre.resize(N+1);
	for(int i=2;i<=N;i++){
		if(np[i]==false){
			prm.push_back(i);
			pre[i]=i;
		}
		for(auto j:prm) if(i*j<=N){
			int k=i*j;
			pre[k]=j;
			np[k]=true;
			if(i%j==0) break;
		}else break;
	}
}

例题：B3716 分解质因子 3

说明一下，prm 存了所有范围内的素数，pre 存了第 \(i\) 个数的最小质因子。

这个板子直接背过就好了。（~~其实是我懒得讲~~）

不等式方程

形如 \(ax+by=c\) 的方程（\(a,b\) 为整数），方程有解当且仅当 \(\gcd(a,b)|c\)

欧几里得算法：\(\gcd(a,b)=\gcd(b,a \bmod b)\)。

\(ax+by=\gcd(a,b)\) 求解：

当 \(a|b\) 时，\(ax+by=\gcd(a,b)\) 解为 \(\begin{cases}x=0\\y=1\end{cases}\)

\[\begin{aligned}\because ax+by&=\gcd(a,b)\\&=\gcd(b,a \bmod b)\\&=bx_1+(a\bmod b)y_1\\&=bx_1+(a-\lfloor\dfrac{a}{b}\rfloor \times b)y_1\\&=bx_1+(a-\lfloor\frac{a}{b}\rfloor \times b)y_1\\&=ay_1+b(x_1-\lfloor\frac{a}{b}\rfloor \times y_1) \end{aligned} \]

\[\therefore \begin{cases}x=y_1\\y=x_1-\lfloor \frac{a}{b} \rfloor \times y_1 \end{cases} \]

\(\therefore\) 可以递归求解。

\(\color{white}{\text{公式对不齐好难受啊。QWQ}}\)

递归函数

void gg(int &x,int &y,int a,int b){
	if(a%b==0){
		x=0,y=1;
	}else{
		int xx,yy;
		gg(xx,yy,b,a%b);
		x=yy;y=xx-a/b*yy;
	}
}

裴蜀定理（写于 2023.4.14）

这个是后补的。QWQ

定义

设 \(a,b\) 是不全为零的整数，则存在整数 \(x,y\) , 使得 \(ax+by=\gcd(a,b)\)。

然后就发现前面的式子求的就是裴蜀定理的式子。

然后写一个我自己发现的东西：（只不过我看过的文章都没讲过，~~可能是因为为太简单了~~）

求 \(ax+by=c\) 的解，其中 \(a,b\) 为整数且 \(\gcd(a,b)|c\)。

首先求出 \(ax+by=\gcd(a,b)\) 的解，设解为 \(\begin{cases}x=x'\\y=y'\end{cases}\)

再设 \(k=\dfrac{c}{\gcd(a,b)}\)，则 \(ax+by=c\) 的解为 \(\begin{cases}x=kx'\\y=ky'\end{cases}\)

然后就没了。QWQ

进一步的结论可以去下面的链接。

裴蜀定理

同余

概念

对两个整数 \(a\)，\(b\)，如果它们除以 d 的余数相同，则称它们模
\(d\) 同余，记作：

\[a \equiv b\pmod d \]

一个小知识

\[a-k \times b=r \to a \equiv r \pmod b \]

（\(k\) 为任意整数）

威尔逊定理（没啥卵用）

正整数 \(p\) 是质数的充要条件为：

\[(p-1)! \equiv -1 \pmod p \]

欧拉函数

\(\varphi \leftarrow\) 就是这个玩意。

定义

欧拉函数 \(\varphi(n)\) 表示小于等于 \(n\)（其实等不等于 \(n\) 无所谓，因为 \(n\) 一定不与 \(n\) 互质）且与 \(n\) 互质的正整数（与 \(n\) 互质即对于一个数 \(i\)，\(\gcd(i,n)=1\) 或者说是 \(n \perp i\)）的个数。

特别的，\(\varphi(1)=1\)。

顺便提一嘴，\(1\) 与任何数都互质。

~~显然，~~ 对于一个正整数 \(a\)，\(a\) 是质数当且仅当 \(\varphi(a)=a-1\)。

性质

积性：如果对于任意两个正整数 \(a,b\)，如果 \(\gcd(a,b)=1\)（即 \(a \perp b\)），\(\varphi(a \times b)=\varphi(a)\times\varphi(b)\)。

欧拉反演：\(\sum\limits_{d \mid n}\varphi(d)=n\)。（\(\sum_{d \mid n}F(d)\) 表示把 \(n\) 以内所有能整除 \(n\) 的数 \(d\) 带入 \(F(d)\) 中求和）

性质三（很重要）：对于任意质数 \(p\)，\(\varphi(p^k)=p^k-p^{k-1}\)。

接下来是举例子时间。QWQ

\[\begin{aligned}\varphi(3 \times 7)&=\varphi(21)\\&=12\end{aligned} \]

\[\begin{aligned}\varphi(3)\times\varphi(7)&=2\times6\\&=12\end{aligned} \]

然鹅，

\[\begin{aligned}\varphi(2 \times 4)&=\varphi(8)\\&=4\end{aligned} \]

\[\begin{aligned}\varphi(2)\times\varphi(4)&=1\times2\\&=2\end{aligned} \]

\[\begin{aligned}&\because \gcd(2,4)\ne1 \\&\therefore \varphi(2 \times 4) \ne \varphi(2)\times\varphi(4)\end{aligned} \]

\[\begin{aligned}\sum\limits_{d \mid 8}\varphi(d)&=\varphi(1)+\varphi(2)+\varphi(4)+\varphi(8)\\&=1+1+2+4\\&=8\end{aligned} \]

性质三证明：小于等于 \(p^k\) 的数有 \(p^k\) 个，其中 \(p,2\times p,3\times p...t\times p\) 与 \(p\) 不互质，~~显然，~~ \(t=p^{k-1}\)，所以与 \(p\) 不互质的数有 \(p^{k-1}\) 个，那么与 \(p\) 互质的数就有 \(p^k-p^{k-1}\) 个，即 \(\varphi(p^k)=p^k-p^{k-1}\)。

计算欧拉函数

单个欧拉函数：设 \(n\) 的唯一分解式（就是质因数分解）为 \(n=p_1^{k_1} \times p_2^{k_2} \times ... \times p_s^{k_s}\)（~~显然，~~ \(p_1\) 到 \(p_s\) 均为质数，且 \(p_1^{k_1},p_2^{k_2}...p_s^{k_s}\) 两两互质），则 \(\varphi(n)=\prod\limits_{i=1}^s \varphi(p_i^{k_i})\)，\(\prod\limits_{i=1}^s \varphi(p_i^{k_i})\) 能用性质三求解（其实就是 \(\varphi(n)=\prod\limits_{i=1}^s (p_i^{k_i}-p_i^{k_i-1})\)）。

线性筛欧拉函数

在线性筛素数的同时可以筛出欧拉函数，设 \(p\) 是 \(i\) 的最小质因子，分三种情况讨论：

\(i\) 为质数，\(\varphi(i)=i-1\)。
\(p\) 是 \(\frac{i}{p}\) 的质因子，\(\varphi(i)=\varphi(\frac{i}{p}) \times p\)。
\(p\) 与 \(\frac{i}{p}\) 互质，\(\varphi(i)=\varphi(\frac{i}{p}) \times \varphi(p)\)。

证明：

显然
设 \(i=p^k \times q\)，其中 \(q\) 不含质因子 \(p\)。则 \(\varphi(i)=\varphi(q) \times \varphi(p^k)=\varphi(q) \times (p^k-p^{k-1})=\varphi(q) \times p(p^{k-1}-p^{k-2})=\varphi(q) \times p \times \varphi(p_{k-1})=\varphi(\frac{i}{p}) \times p\)
根据积性可得。

例题：P2158 [SDOI2008] 仪仗队。

假如 C君 在仪仗队的左前方，坐标为 \((0,0)\)。

首先可以发现，对于一个坐标 \((i,j)\)，C君 能看到这个位置当且仅当 \(\gcd(i,j)=1\)，并且在与 C君 位置相交的对角线左右两边能看到的位置对称。

可以推个柿子。

当 \(n\le 2\) 时：

\[ans=2\sum\limits^{n-1}_ {i=1}\sum\limits^{i-1}_ {j=1} [\gcd(i,j)=1] +3 \]

\[ans=2\sum\limits^{n-1}_ {i=1} \varphi(i) +3 \]

用线性筛欧拉函数即可，记得当 \(n=1\) 时特判一下。

代码：

#include<bits/stdc++.h>
#define XD 114514
#define MAXN 40010
using namespace std;
int n;
int phi[MAXN];
bool np[MAXN];
vector<int> prm,pre;
long long ans;
void gg(){
	pre.resize(n+10);
	for(int i=2;i<=n;i++){
		if(np[i]==false){
			phi[i]=i-1;
			pre[i]=i;
			prm.push_back(i);
		}
		for(int j=0;j<prm.size();j++){
			if(i*prm[j]<=n){
				int k=i*prm[j];
				pre[k]=prm[j];
				np[k]=true;
				if(i%prm[j]==0){
					phi[k]=phi[i]*prm[j];
					break;
				}else{
					phi[k]=phi[i]*phi[prm[j]];
				}
			}else break;
		}
	}
}
int main(){
	cin>>n;
	if(n==1) cout<<0;
	else{
		gg();
		for(int i=1;i<=n-1;i++) ans+=phi[i];
		cout<<(ans+1)*2+1;
	}
	return 0;
}

欧拉定理

对任意正整数 \(a,m\)，\(\gcd(a,m)=1\)，一定有：\(a^{\varphi(m)} \equiv 1 \pmod m\)。

逆元

逆元补充（by 2023.5.11）

定义

对于任意正整数 \(x\) 满足 \(x \times x_0 \equiv 1 \pmod p\)，则称 \(x_0\) 为 \(x\) 在模 \(p\) 同余下的逆元（其实就跟普通的 \(x \times x^{-1}=1\) 中的 \(x^{-1}\) 差不多，只不过 \(x_0\) 是在模 \(p\) 同余下，而且在模 \(p\) 同余下，\(x\times x_0=1\)，然后就可以得出 \(x^k \times x_0 \equiv x^{k-1} \pmod p\)）

为了方便理解，我就先把下文中所有的字母下面带 \(0\) 的都为这个字母代表的数在模某一个数同余下的逆元。（因为我在听课时老师是用 \(x^{-1}\) 表示 \(x\) 在模 \(p\) 同余下的逆元QWQ）

性质（这些记住就行QWQ）

逆元存在性定理：\(x\) 在模 \(p\) 同余下存在逆元当且仅当 \(\gcd(x,p)=1\)。

推论：当且仅当模数 \(p\) 是质数时，\([1, p − 1]\) 内所有整数都存在模 \(p\) 下的逆元。 \(0\) 没有逆元。

逆元唯一性定理：模 \(p\) 同余下，一个整数 \(x\) 的逆元若存在，则唯一。

定理：在模质数 \(p\) 同余下， \([1, p − 1]\) 内所有整数的逆元互不相同。

定理：一个数的逆元的逆元等于它自身。

计算逆元

先上例题。

P1082 [NOIP2012 提高组] 同余方程

根据逆元定义可得这是一道求逆元板子题（显然）。

因为题目说输入数据保证一定有解，根据逆元存在性定理可得 \(\gcd(a,b)=1\)。

~~开始求逆元喽。~~

\[a \times x \equiv 1 \pmod b \]

\[\therefore a\times x =1 + b \times k \]

\[\therefore a\times x + b \times k = 1 \]

（由于 \(k\) 为任意整数，我们不知道它是正数还是负数，就把前面的正负号省略了）

然后可以发现，这不就是一个不定方程吗。（因为 \(a,b\) 为已知量，只需求 \(x\)）

在前面我们知道 \(\gcd(a,b)=1\)，所以可以用递归求解即可。

最后记得把 \(x\) 取模到 \([1,b-1]\) 的范围即可。QWQ

代码如下。

#include<bits/stdc++.h>
#define XD 114514
#define int long long
using namespace std;
inline void gg(int &x,int &y,int a,int b){
	if(a%b==0){
		x=0,y=1;
	}else{
		int xx,yy;
		gg(xx,yy,b,a%b);
		x=yy;
		y=xx-a/b*yy;
	}
}
signed main(){
	int a,b,x,y;
	cin>>a>>b;
	gg(x,y,a,b);
	cout<<(x%b+b)%b;
	return 0;
}

当然也可以像下面这样写。

#include<bits/stdc++.h>
#define XD 114514
#define int long long
using namespace std;
inline void gg(int &x,int &y,int a,int b){
	if(a%b==0){
		x=0,y=1;
		return;
	}
	gg(y,x,b,a%b);
	y-=a/b*x;
}
signed main(){
	int a,b,x,y;
	cin>>a>>b;
	gg(x,y,a,b);
	cout<<(x%b+b)%b;
	return 0;
}

欧拉定理的继续

欧拉定理有一个前提条件就是 \(\gcd(a,m)=1\)，根据逆元存在性定理就可得出这个 \(a\) 在模 \(m\) 同余下一定有逆元。让我们推个式子。QWQ

\[a^{\varphi(m)} \equiv 1 \pmod m \]

\[a^{\varphi(m)}\times a_0 \equiv a_0 \pmod m \]

\[a^{\varphi(m)-1} \equiv a_0 \pmod m \]

然后我们就得到了另一个求逆元的方法。（虽然不是很好用）

但是当 \(m\) 是质数时，\(a^{\varphi(m)} \equiv 1 \pmod m\) 就可以转化成 \(a^{m-1} \equiv 1 \pmod m\)~~，于是费马小定理出现了~~。

费马小定理

对任意整数 \(a\) 和质数 \(p\)，\(a^{p-1} \equiv 1 \pmod p\)。

根据式子可以推出：

\[a_0 \equiv a^{p-2} \pmod{p} \]

然后我们就又双叒叕得到了一个求逆元的方法（用快速幂求一下 \(a^{p-2} \bmod p\) 即可）。

上个题QWQ P2613 【模板】有理数取余

求 \(\frac{a}{b} \bmod 19260817\) 的值。

让我们算一算吧。

\[\frac{a}{b} \bmod 19260817 \]

\[a \times b_0 \bmod 19260817 \]

所以我们只需算出 \(b\) 模 \(19260817\) 同余下的逆元。由于 \(19260817\) 为一个质数，用费马小定理求即可。

而无解的情况就是 \(b\) 是 \(19260817\) 倍数，那么 \(b \bmod 19260817\) 一定等于 \(0\)。

~~直接上代码。~~

#include<bits/stdc++.h>
#define XD 114514
#define mod 19260817
using namespace std;
inline long long read(){
	char ch=getchar(),h;long long w=0;
	while(ch>'9' or ch<'0') h=ch,ch=getchar();
	while(ch>='0' and ch<='9') w=(w*10+(ch-'0'))%mod,ch=getchar();
	if(h=='-') w=-w;
	return w;
}
long long a,b;
inline long long gg(long long x,long long k){
	//求 x 在模 mod 同余下的逆元，即求 x^(mod-2)%mod 的值
	//这里 k 就表示 mod-2 的值 
	long long ans=1;
	while(k){
		if(k&1){
			ans*=x;ans%=mod;
		}
		x*=x;x%=mod;
		k>>=1;
	}
	return ans;
}//快速幂是啥偶就不讲了QWQ 
int main(){
	a=read(),b=read();
	if(b==0) cout<<"Angry!\n";
	else cout<<a*gg(b,mod-2)%mod;
	return 0;
}

线性求逆元

设 \(inv_i\) 表示 \(i\) 的逆元，有递推式：

\[inv_i \equiv - \lfloor \frac{p}{i} \rfloor \times inv_{p \bmod i} \pmod p \]

边界为 \(inv_1 = 1\)。

~~又要开始推式子了。~~

\[p=i \times k +r (r \in [1,n)) \]

\[0 \equiv i \times k + r \pmod p \]

\[r \equiv -i \times k \pmod p \]

\[r \times r_0 \times i_0 \equiv -i \times i_0 \times r_0 \times k \pmod p \]

\[i_0 \equiv -k \times r_0 \pmod p \]

\[inv_i \equiv -\lfloor \frac{p}{i} \rfloor \times r_0 \pmod p \]

\[inv_i \equiv -\lfloor \frac{p}{i} \rfloor \times inv_{p \bmod i} \pmod p \]

再解释一下，我们刚开始设 \(p=i \times k +r\)，其中 \(r \in [1,n)\)，~~显然，~~\(k=\lfloor \frac{p}{i} \rfloor\)，\(r=p \bmod i\)，这样应该能看懂了吧。QWQ

P3811 【模板】乘法逆元

下面是代码。

#include<bits/stdc++.h>
#define XD 114514
#define MAXN 3000010
using namespace std;
int n,p,inv[MAXN];
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>p;
	inv[1]=1;
	for(int i=2;i<=n;i++){
//		inv[i]=(1ll*-(p/i)*inv[p%i]%p+p)%p;
		inv[i]=1ll*(p-p/i)*inv[p%i]%p;//这两个算式等价，只不过这个少取模一次 
		//实测，在P3811中第一个用398ms，第二个用338ms
	}
	for(int i=1;i<=n;i++) cout<<inv[i]<<'\n';
	return 0;
}

~~说句闲话，~~我刚开始做这道题时一直 \(\color{black}{TLE}\) 了两个点，最后把换行符 endl 改为 '\n' 就 \(\color{green}{AC}\) 了，这个故事告诉我们，珍爱生命，远离 endl。

B3717 组合数问题

首先知道：

\[C^m_n=\frac{n!}{m!(n-m)!} \]

~~显然：~~

\[C^m_n \equiv \frac{n!}{m!(n-m)!} \pmod {998244353} \]

之后就把 \(998244353\) 当做 \(p\) 就行了~~不然打一个九位数太麻烦了~~，而且一个数 \(x\) 的逆元就当做 \(x^{-1}\) 就行了。

\[\frac{n!}{m!(n-m)!} \bmod p= n! \times (m!)^{-1} \times [(n-m)!]^{-1} \bmod p \]

然后求 \((m!)^{-1}\)，~~显然：~~

\[(m!)^{-1} \equiv 1^{-1} \times 2^{-1} \times 3^{-1} \times ... \times (m-1)^{-1} \times m^{-1} \pmod p\]

所以先线性求一遍逆元，然后预处理出所有阶乘的逆元即可。

上代码。

#include<bits/stdc++.h>
#define XD 114514

using namespace std;
int T,N;
const int p=998244353;
int ans;
int main(){
	ios::sync_with_stdio(false);
	cin>>T>>N;
	vector<int> inv(N+1),a(N+1),b(N+1);
	inv[1]=1;//inv_i 表示 i 的逆元 
	a[1]=1;//a_i 表示 i!的值 
	b[0]=b[1]=1;//b_i 表示 i! 的逆元的值 
	for(int i=2;i<=N;i++){
		inv[i]=1ll*(p-p/i)*inv[p%i]%p;
		a[i]=1ll*a[i-1]*i%p;
		b[i]=1ll*b[i-1]*inv[i]%p;
	}
	while(T--){
		int n,m,num=1;
		cin>>n>>m;
		num=1ll*a[n]*b[m]%p*b[n-m]%p;
		ans^=num;
	}
	cout<<ans;
	return 0;
}

中国剩余定理（CRT）

它是用来解决一个问题的。

问题

给定 \(n\) 个线性同余方程：

\[\begin{cases} x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \\ ... \\ x \equiv a_n \pmod {m_n} \end{cases} \]

其中保证 \(m_1,m_2,...,m_n\) 两两互质。求 \(x\) 的通解。

定理

上面的方程组有解，且按如下方式构造：

记 \(M=\prod\limits^n_{i=1}m_i\) ，\(M_i=\frac{M}{m_i}\)，\(t_i\) 为 \(M_i\) 在模 \(m_i\) 同余下的逆元。

则方程组的唯一通解是：

\[x \equiv \sum\limits^n_{i=1}a_i t_i M_i \pmod M \]

证明

~~显然：~~

\[\gcd(M_i,m_i)=1 \]

且，

\[M_it_i \equiv 1 \pmod {m_i} \]

（能够保证 \(M_i\) 在模 \(m_i\) 同余下一定有逆元）

\[\therefore a_iM_it_i \equiv a_i \pmod{m_i} \]

另外，对于一个 \(j\)（\(j \ne i\)），由于 \(m_i | M_j\)，于是 \(M_j \equiv 0 \pmod{m_i}\)。

\[\therefore a_iM_it_i+m_jM_jt_j \equiv a_i \pmod{m_i} \]

\[\therefore a_iM_it_i + \sum\limits^n_{j=1,i\ne j} a_jM_jt_j \equiv a_i \pmod{m_i} \]

\[\sum\limits^n_{i=1} a_iM_it_i \equiv a_i \pmod{m_i} \]

这就验证了 \(x=\sum\limits^n_{i=1} a_iM_it_i\) 是方程组的一组特解。

运用小学知识（~~其实就是我懒得证明~~）可得每两组相邻特解之间相差为 \(M\) 的倍数，于是 \(x+kM\) 也是一个特解，由此，通解唯一性得证。

例题

P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪

模板题，直接上代码。

#include<bits/stdc++.h>
#define XD 114514
#define MAXN 20
#define int long long
using namespace std;
int n;
void gg(int &x,int &y,int a,int b){//求逆元
	if(a%b==0){
		x=0,y=1;
		return;
	}
	gg(y,x,b,a%b);
	y-=a/b*x;
}
int a[MAXN],b[MAXN],M[MAXN],m=1,t[MAXN],ans;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];//x=ai*k+bi -> x mod ai=bi mod ai
		m*=a[i];
	}
	for(int i=1;i<=n;i++){
		M[i]=m/a[i];
		int x=0,y=0;
		gg(x,y,M[i],a[i]);
		t[i]=(x%a[i]+a[i])%a[i];
	}
	for(int i=1;i<=n;i++){
		ans+=b[i]*t[i]%m*M[i]%m;
		ans%=m;
	}
	cout<<ans;
	return 0;
}

P3868 [TJOI2009] 猜数字

\[b | (n-a_i) \]

\[n-a_i \equiv 0 \pmod{b_i} \]

\[n \equiv a_i \pmod{b_i} \]

然后套模板即可。

Lucas定理

定义

对于一个质数 \(p\)，

\[\dbinom{n}{m} \bmod p =\dbinom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor} \cdot \dbinom{n \bmod p}{m \bmod p}\bmod p \]

变成我更习惯的写法就是：

\[C^m_n \bmod p = C^{\lfloor \frac{m}{p} \rfloor}_ {\lfloor \frac{n}{p} \rfloor} \cdot C^{m \bmod p}_ {n \bmod p} \bmod p \]

证明我暂时不会，先放个链接QWQ。

链接

当 \(p\) 不为质数时，就需要用到 exLucas 定理了。

具体的上面的链接也有，我就不说了QWQ。（~~其实我就是不会~~）

例题

P3807 【模板】卢卡斯定理/Lucas 定理

模板题。~~听君一席话，如听一席话。~~

直接上代码。

#include<bits/stdc++.h>
#define XD 114514

using namespace std;
int t;
int qpow(int x,int y,int p){//快速幂 
	int ans=1;
	while(y){
		if(y&1) ans=1ll*ans*x%p;
		x=1ll*x*x%p;
		y>>=1;
	}
	return ans;
}
int C(int n,int m,int p){//组合数 
	if(n<m) return 0;
	int a=1,b=1;
	for(int i=1;i<=n;i++) a=1ll*a*i%p;
	for(int i=1;i<=m;i++) b=1ll*b*i%p;
	for(int i=1;i<=n-m;i++) b=1ll*b*i%p;
	return 1ll*a*qpow(b,p-2,p)%p;
}
int Lucas(int n,int m,int p){//Lucas 递推 
	if(n<p and m<p) return C(n,m,p);
	return 1ll*Lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
}
int main(){
	cin>>t;
	while(t--){
		int n,m,p;
		cin>>n>>m>>p;
		cout<<Lucas(n+m,m,p)<<'\n';
	}
	return 0;
}

容斥原理

首先我把关于容斥原理的符号及定义复制下来~~以便以后查看~~。

以下内容来自这里。

~~说句闲话，我开始了解集合也是开始于上面的链接。~~

+++++++++++++++ 虚假分割线 ++++++++++++++++++

集合是数学中的一个概念，用通俗的话来讲就是：一大堆数在一起就构成了集合。

集合有如下的特性：

无序性：任一个集合中，每个元素的地位都是相同的，元素之间是无序的。
互异性：一个集合中，任何两个元素都认为是不相同的，即每个元素只能出现一次。
确定性：给定一个集合，任给一个元素，该元素或者属于或者不属于该集合，二者必居其一，不允许有模棱两可的情况出现。

元素 \(a\) 属于集合 \(A\) 记作 \(a\in A\)，反之则记作 \(a\notin A\)。

如果对于任意集合 \(A\) 内的元素 \(a\)，都有 \(a\in B\)，则称 \(A\) 为 \(B\) 的子集，记作 \(A\subseteq B\)。

若集合 \(A\)，\(B\) 满足集合 \(A\) 中的元素都能够在 \(B\) 中找到，且集合 \(B\) 中的元素都能在 \(A\) 中找到，则称集合 \(A\) 与 \(B\) 相等，记作 \(A=B\)。

若一个集合中不存在任何元素，则称该集合为空集，记作 \(\varnothing\)。空集是所有集合的子集。

一个集合内的元素个数称为该集合的大小。\(A\) 集合的大小可记作 \(|A|\)。

集合 \(C\) 是集合 \(A\) 与 \(B\) 的交集，当且仅当对于任何元素 \(a\in C\)，有 \(a\in A\) 且 \(a\in B\)，并且对于任何元素 \(b\notin C\)，有 \(b\notin A\) 或 \(b\notin B\)。记作 \(C=A\cap B\)。

集合 \(C\) 是集合 \(A\) 与 \(B\) 的并集，当且仅当对于任何元素 \(a\in C\)，有 \(a\in A\) 或 \(a\in B\)，并且对于任何元素 \(b\notin C\)，有 \(b\notin A\) 且 \(b\notin B\)。记作 \(C=A\cup B\)。

简单地说，交集是由所有同时属于两个集合的元素所构成的，就像两个集合相交；而并集是由所有属于其中任意一个集合的元素所构成的，就像两个集合合并。

设集合 \(A\subseteq U\)，称集合 \(B\) 为集合 \(A\) 关于集合 \(U\) 的补集，当且仅当 \(B\) 集合内的所有元素恰好为所有属于 \(U\) 集合但不属于 \(A\) 集合的元素。记作 \(B=\complement_UA\)。显然可以得到这样的一个式子：\(|U|=|A|+|\complement_UA|\)，对于任何 \(A \subseteq U\) 成立。

简单地说，补集就是与一个集合互补的集合，每个元素恰好在其中两者之一。

特别地，对于形如 \(\{x|a\le x\le b\}\) 的集合，可以记作 \([a,b]\)。其中，如果左侧符号改为小于号，则左侧中括号改为小括号。右侧同理。

+++++++++++++++ 虚假分割线 ++++++++++++++++++

我们有 \(A,B,C\) 三个集合，求 \(|A \cup B \cup C|\) ，可以列出式子：

\[|A \cup B \cup C|=|A|+|B|+|C|-|A \cap B|-|A \cap C|-|B \cap C|+|A \cap B \cap C| \]

如果我们有 \(n\) 个集合 \(P_1,P_2,...,P_n\)，则：

\[|\bigcup\limits_{i=1}^n P_i|=\sum\limits_{S\subseteq[1,2,...,n]}(-1)^{|S|-1}|\bigcap\limits_{s\in S}P _ s|\]