整除

如果a能被b整除，a=b*q，q为一整数记作b|a,a是被除的那个

同余

如果a和bmod m 是同一个值，则称a和b同余，记作a (三横线） b(mod m)

例如： 3 和 8 关于5 同余 因为 3%5=3,8%5=3

重要性质： 

     （a+b)%c=a%c+b%c
     (a*b)%c=(a%c*b%c)%c
     (a^b)%c=(a%c^b)%c

唯一分解定理

任何大于1的正整数n都可以被分解为若干质数的乘积

约数个数 例如 72=2^33^2 ，而72有 1 2 3 4 6 8 9 12 18 24 36 72 12个约数
，而我可以从2^3 中提取出0个2,1个2，两个2，三个2把其他的数放到另一边，这样我们就可以得到4个约数，3也同理，用一下分配率，就可以得到约数个数为34=12

约数和 因为约数是从2和3中随机挑出若干个数进行分配，所以用分配率可得约数和为

(1+2+2^2+2^3)(1+3+3^2)

费马小定理

如果p是质数且a与p互质，则

a^(p-1)%p=1(a的p-1次方和1关于p同余）

互质指的是 二者除了1以外没有相同的约数

求质数的方法

埃氏筛

线性筛

欧拉函数

概念：表示0到n-1中与n互素的数的个数

积性函数：如果 m和n互质 ，则f(mn)=f(m)f(n)

欧拉函数的性质：

  1. 对于质数p f(p)=p-1
  2. 如果n=p^k,则f(n)=p^k-p^k-1
  3. 欧拉函数是积性函数，但不是完全积性函数，当n为质数时成立，当m=2,n为奇数时，f(2*n)=n
  4. n>2时 f(n)是偶数
  5. 与n互质的数的和为 f(n)*n/2
  6. n的因数的欧拉函数的和为n

模意义下的乘法逆元

例 1/5%7=?

3*5%7=1,所以1/5的逆元是3，所以1/5%7=3

逆元的求法

1 费马小定理

a*a^-1%p=1,a^p-1%p=1

可得 a^-1%p=a^p-2%p，然后用快速幂。但是费马小定理要求必须要是素数

2 线性求逆元（不理解）

公式：inv(a)=-p/a*inv(p%a)%p;

inv[1]=1;
for(int i=2;i<=n;++i){
inv[i]=((1ll*(-p/i)*inv[p%i]%p)+p)%p;
}

3 扩展欧几里得法

exgcd

exgcd用来求解ax+by=c，其中a，b，c都为整数

裴蜀定理

不定方程 ax+by=c存在整数解当且仅当gcd(a,b)|c ，当存在一组整数解时，必存在无限组解
ax+by=gcd(a,b)=>bx1+a%by1=gcd(b,a%b)=>x=x1,y=x1-(a/b)y1

x=x1+kb/gcd(a,b) , y= y1-ka/gcd(a,b)

之后一直求解直到x=1,y=0,这时b=0,所以gcd(a,b)=a,方程一定成立

在这里我们可以用递归反推，把x=1,y=0带入方程，一步步向上推

void exgcd(int a,int b,int &x,int &y){
if(b==0){
x=1;
y=0;
return ;
}
int x1,y1;
exgcd(b,a%b,x1,y1);
x=y1;
y=x1-(a/b)*y1;
}

这里我们就可以得到第三种方法

求逆元可以转化为：求关于x的同余方程ax（三横）1 mod b的最小正整数解

ax%b=1 ax=kb+1

即 ax-by=1

最后 x1%b+b即是答案

可以看这篇博客

排列组合

求C(m,n)%p的值

可变成 (n!/m!(n-m)!)%p

之后就用费马小定理求逆元

int ksm(int a,int b,int p){
int ret=1;
while(b){
if(b&1) ret=1ll*ret*a%p;
a=1ll*a*a%p;
b>>=1;
}
return ret%p;
}
int fac[maxn];
int inv(int x){
return ksm(x,p-2,p);
}
int C(int n,int m){
int qwq=1ll*fac[n]*inv(fac[n-m])%p;
return 1ll*qwq*inv(fac[m])%p;
}
int main(){
fac[0]=1;
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
fac[i]=1ll*fac[i-1]*i%p;
}
printf("%d",C(n,m));
return 0;
}