加法原理 乘法原理 容斥原理

组合数性质

1：C(n,0）=C(n,n)=1

2：C(n,k)=C(n,n-k)

3：C(n,k)+C(n,k+1)=C(n+1,k+1)

4：C(n,k+1)= C(n,k)*（n-k）/(k + 1）

 

素数表

const int maxn = 10000000 + 10;const int maxp = 700000;int vis[maxn];//vis[i]=1，i是合数int prime[maxp];//筛素数void sieve(int n){    int m = (int)sqrt(n + 0.5);    memset(vis, 0, sizeof(vis));    for(int i = 2; i <= m; i++)         if(!vis[i])            for(int j = i * i; j <= n; j+= i)                vis[j] = 1;    }int gen_primes(int n){    sieve(n);    int c = 0;    for(int i = 2; i <= n; i++)        if(!vis[i])            prime[c++] = i;    return c;}

欧几里得和扩展欧几里得

typedef long long LL;LL gcd(LL a, LL b){    return b == 0?a:gcd(b, a % b);}//求整数x和y， 是的ax+by=d， 且|x| + |y|最小。其中d=gcd（a,b)//即使a， b在int范围，x和y也有可能超出int范围void exgcd(LL a, LL b, LL& d, LL& x, LL& y){    if(!b){        d = a;x = 1; y = 0;    }    else{exgcd(b, a % b, d, y, x);y -= x* (a / b);}}

 

 

幂取模

LL pow_mod(LL a, LL p, LL mod){    if(p == 0) return 1;    LL ans = pow_mod(a, p / 2, mod);    ans = ans * ans % mod;    if(p % 2 == 1) ans = ans * a % mod;    return ans;}

 

 

欧拉phi函数

phi(x) = 不超过x且和x互素的整数个数

int euler_phi(int n){    int m = (int)sqrt(n + 0.5);    int ans = n;    for(int i = 2; i <= m; i++)        if(n % i == 0){            ans = ans / i * (i - 1);            while(n % i == 0) n /= i;        }        if(n > 1) ans = ans / n * (n - 1);}int phi[maxn];void phi_table(int n){    for(int i = 2; i <= n; i ++)phi[i] = 0;    phi[1] = 1;    for(int i = 2; i <= n; i++){        if(!phi[i]){            for(int j = i; j <= n; j += i){                if(!phi[j])                    phi[j] = j;                phi[j] = phi[j] / i * (i - 1);            }        }    }}

 

剩余系 整数n所有可能的余数

完全剩余系Zn{0， 1， 2， ... ， n - 1}， 每个元素代表所有与他同余的整数，每个元素对应一个同余等价类

简化剩余系（缩系） 完全剩余系中与n互素的元素

模加法 模乘法

模乘法的逆  Zn中的两个元素a和b满足ab=1

在Z15中7^-1 = 13 ， 3/7=9的含义是“假定有两个整数a和b， 其中a/b是整数，且a和b除以15的余数分别为3和7， 则a/b除以15的余数等于9”

//计算模n下a的逆，如果不存在逆，返回-1LL inv(LL a, LL n){    LL d, x, y;    gcd(a, n, d, x, y);    return d == 1?(x + n) % n : -1;}