n! 分解质因数

1：找到所有质因数p[i]
2:遍历： n / p + n / p^2 +.....

约数个数

n = (p1 ^ c1) + (p2 ^ c2);
ans = (c1 + 1)(c2 + 1);

欧拉函数

1 - n 中和n 互质的个数
n = (p1 ^ c1) * (p2 ^ c2)
u(n) = n * (1 - 1 / p1) * (1 - 1 / p2);
求欧拉函数

void init(int n)
{
    phi[1] = 1;
    for(int i  = 2; i <= n; ++i)
    {
        if(!vis[i])
        {
            prime[cnt ++] = i;
            phi[i] = i - 1;    
        }    
        for(int j = 0; prime[j] * i <= n; ++i)
        {
            vis[prime[j] * i] = 1;
            if(i % prime[j] == 0)
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }    
} 

扩展欧几里得

ax + by = d =>
x = x0 + k * (b / d);
y = y0 - k * (a / d);

ax == c(% b) => ax + by = c;

欧拉定理

a^u(n) == 1(mod n)[a, n 互质]

中国剩余定理

x =
Ti 为 mi逆元
Mi 为 M / mi

组合计数

递推法

隔板法

加法原理 / 乘法原理

组合数 / 排列数

1： 递推法
2：阶乘 + 逆元
4: 阶乘求质因子 然后相减
等式 k - 1个板子
不等式 k 个 板子

lucas

C(a,b) = C(a % p, b % p) * C(a / p, b / p)

catalan数列

C(12,6) - C(12,5)
C(2n,n) - C(2n,n-1)