@Bei-S
2019-02-14T06:31:15.000000Z
字数 3673
阅读 1361
基础数论
数论
所谓万丈深渊，下去，也是前程万里。——木心
这部分内容比较枯燥，但非常重要，自己仔细推一下！！！
计数原理
加法原理
如果事件A有p种生产方式，B有q种生产方式，则事件（A或B）有（p+q）种生产方式
注意：事件A和事件B产生的方式不重合
乘法原理
如果事件A有p种生产方式，B有q种生产方式，则事件（A与B）有（p*q）种生产方式
注意：事件A和事件B必须互相独立
加法原理和乘法原理都可以推广到n个事件使用
容斥原理
要计算几个集合并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的部分，再加回所有三个集合相交的部分，再减去所有四个集合相交的部分，依此类推，一直计算到所有集合相交的部分。
抽屉原理(鸽巢原理)
桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面至少放两个苹果。
二项式定理
其中每个 
为一个称作二项式系数的特定正整数，其等于 
。这个公式也称二项式公式或二项恒等式。使用求和符号，可以把它写作
快速幂&&快速乘
快速幂:
ll qpow(ll a,ll b){ll ans=1;while(b){if(b&1) ans*=a;a*=a;b>>=1;}return ans%k;}
快速乘：
inline ll Mul(ll a,ll b){int ret=0;while(b){if(b&1) ret+=a;a+=a;b>>=1;}return ret;}
扩展欧几里得
唯一分解定理
任何一个大于1的自然数N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积。
比如，1260=2*2*3*3*5*7
费马小定理
p为素数，a为正整数，a与p互质，则 a^(p-1)≡ 1 (mod p) 。
欧拉小定理
a^φ(m) ≡ 1 (mod m)，(a与m互质) 。
欧拉函数 φ(m)
φ(m)表示不超过m的与m互质的数的个数。
裴蜀定理
若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。
推广:n个整数，a1,a2,a3......an为n个整数，d是它们的最大公约数，那么存在整数x1......xn使得x1*a1+x2*a2+...xn*an=d。
素数筛
A.埃氏筛法:只需要把所有的 2 的倍数，3 的倍数，…… 都排除掉那么剩下的都是素数
时间复杂度
考虑优化：我们只让每个合数被它的最小质因子筛去，就能保证复杂度是
B.线性筛
inline void pre(){vis[0]=vis[1]=1;for(int i=2;i<=n;i++){if(!vis[i]) pri[++cnt]=i;for(int j=1;j<=cnt&&pri[j]*i<=n;j++){vis[pri[j]*i]=1;if(i%pri[j]==0) break;}}}
欧几里得算法(辗转相除)
引理：
证明:设a=p*b+r,r=a%b，c=gcd(a,b)
设a=x*c,b=y*c,其中x,y互质
r=a-p*b=x*c-p*y*c=(x-p*y)*c
当y与x-p*y互质时，gcd(b,r)=c
证明互质:
假设不互质，设y=n*k,x-p*y=m*k,且k>1(n,m互质)
所以 x-p*n*k=m*k
x=k*（m+n*p）
则a=x*c=k*(m+n*p)*c,b=n*k*c
此时gcd(a,b)=kc，与原命题矛盾
故y与x-p*y互质得证
当a%b==0时，gcd(a,b)=b
扩展欧几里得(exgcd)
用于求解不定方程，线性同余方程，逆元
引理:存在x,y使得gcd(a,b)=a*x+b*y
证明：b=0时，gcd(a,b)=b,x=0,y=1
b!=0时，设a*x1+b*y1=gcd(a,b)=gcd(b,a%b）=b*x2+(a%b)*y2
因为a%b=a-a/b*b
所以 a*x1+b*y1=b*x2+（a-a/b*b）*y2
a*x1+b*y1=a*y2+b*(x2-a/b*y2)
x1=y2,y1=x2-a/b*y2
所以递推可得第一组解
int exgcd(int a,int b,int &x,int &y){if(b==0){x=1;y=0;return a;}int g=exgcd(b,a%b,x,y);int t=x;x=y;y=t-a/b*y;return g;}
解不定方程/线性同余方程:
参考exgcd详解
逆元
首先说明逆元的概念，类似于倒数的性质。
方程ax≡1(mod p),的解称为a关于模p的逆，当gcd(a,p)==1（即a，p互质）时，方程有唯一解，否则无解。
对于一些题目会要求把结果MOD一个数，通常是一个较大的质数，对于加减乘法通过同余定理可以直接拆开计算，但对于(a/b)%MOD这个式子，是不可以写成(a%MOD/b%MOD)%MOD的，但是可以写为(a*b^-1)%MOD,其中b^-1表示b的逆元。
求法：
A. 费马小定理
费马小定理(Fermat's little theorem)是数论中的一个重要定理，在1636年提出，其内容为： 假如p是质数，且gcd(a,p)=1，那么 a(p-1)≡1（mod p），即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。
意思很明了，由上方的公式很容易推导出:a*a(p-2)≡1（mod p）对于整数a，p，a关于p的逆元就是a^(p-2),直接快速幂解之即可，但注意这个定理要求a,p互质！
inv[i]=qpow（i，p-2）
B.线性递推
inv[1] = 1;for(i=2;i<M;++i) inv[i]=(M-M/i)*inv[M%i]%M;
首先我们有一个
设
放到%M意义下得
同时乘上 得到
C.exgcd
因为
所以可以写作
gcd（a,p）=1
求解即可
组合数问题
排列问题
从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的无重排列。排列的全体组成的集合用 A(n,r)表示。当r=n时称为全排列。一般不说可重即无重。可重排列的相应记号为 A(n,r)。
n个数，k个位置，多少排列方法？
组合问题
n个不同元素中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合。组合的全体组成的集合用C(n,r)表示，对应于可重组合C(n,r)
n个数，k个位置，多少排列方法(顺序无关)？
组合数性质
对于0≤r≤n,有C(n,r)=C(n,n-r)
C(n,r)=C(n-1,r)+C(n-1,r-1)
C(n,0)+C(n+1,1)+C(n+2,2)+ …+C(n+r,r)=C(n+r+1,r)
C(n,l)*C(l,r)=C(n,r)*C(n-r,l-r)
C(n,0)+C(n,1)+…+C(n,n-1)+C(n,n)=2n
C(n,0)-C(n,1)+C(n,2)-…±C(n,n)=0
C(m+n,r)=C(m,0)*C(n,r)+C(m,1)*C(n,r-1)+…+C(m,r)*C(n,0)
C(m+n,m)=C(m,0)*C(n,0)+C(m,1)*C(n,1)+…+C(m,m)*C(n,m)
错排
n个有序的元素应有n!个不同的排列，如若一个排列使得所有的元素不在原来的位置上，则称这个排列为错排；有的叫重排。
递推公式
组合数逆元
中国剩余定理
欧拉函数
在数论中，对于正整数N,少于或等于N ([1,N]),且与N互质的正整数(包括1)的个数，记作φ(n)。
φ函数的值：
φ(x)=x(1-1/p(1))(1-1/p(2))(1-1/p(3))(1-1/p(4))…..(1-1/p(n)) 其中p(1),p(2)…p(n)为x
的所有质因数;x是正整数; φ(1)=1(唯一和1互质的数，且小于等于1)。注意：每种质因数只有一个。
例如:
φ(10)=10×(1-1/2)×(1-1/5)=4;
1 3 7 9
φ(30)=30×(1-1/2)×(1-1/3)×(1-1/5)=8;
φ(49)=49×(1-1/7)=42;
