数论初步

数论

---

逆元求解

费马小定理

假如a是一个整数，b是一个素数，$gcd(a,p)=1$,则
$a^{p-1}\equiv1(mod(p))$
应用：

• 降次：$a^bmod(p)=a^{(b)mod (p)}mod(p)$
• 质数逆元：$a^{-1}mod(p)=a^{p-2}mod(p)$

欧拉定理

若$n,a$为正整数，且$n,a$互质，则
$a^{\phi(n)}\equiv 1(mod(n))$
费马小定理是欧拉定理的特殊情况，因为$n$为素数时，$\phi(n)=n-1$。
拓欧降次：

• 当$n>1$时,$a^b\%n=a^{b\%\phi(n)}\%n$
• 当$b\leq\phi(n)$时，暴算
• 当$b>\phi(n)$时，$a^b\%n=a^{b\%\phi(n)}\%n$
  拓欧解方程
• 求解$a\equiv 1(mod(q)),x>0$
  则x解集为$\phi(q)$的约数与倍数。

实践

给定$a,p(p>1),gcd(a,p)=1$,求$a$在模$p$意义下的逆元。

• 用Exgcd解方程$ax\equiv 1(mod(p))$
  即$ax+by=1$

int exgcd(int a,int b,int &d,int &x,int &y)
{
    if(!b) x=1,y=0,d=a;
    else exgcd(b,a%b,d,y,x),y-=x*(a/b);
}
{
  re int a;
  exgcd(i,p,g,x,y);
  while(x<0)    x+=p;
  printf("%d\n",x);
}

• 利用欧拉定理$a^{\phi(n)}\equiv1(mod(n))$
  有式$a^{-1}\equiv a^{\phi(n)-1}(mod(n))$
• n为质数时，费马小定理
  $a^{-1}\equiv a^{n-2}(mod(n))$
• 线性求解
  $inv[i]=(p-p/i)*inv[p\%i]$

---

矩阵乘法

struct matrix{
    int a[100][100];
    matrix()
    {
      memset(a,0,sizeof(a));
    }
    int * operator [](int x)
    {
        return a[x];
    }
    matrix operator *(matrix b)
    {
        matrix c;
        for(int i=0;i<l;i++)
        for(int j=0;j<l;j++)
        for(int k=0;k<l;k++)
        c[i][k]=(c[i][k]+1ll*a[i][j]*b[j][k])%w;
        return c;
    }
}S,T;

---

高斯消元

专题总结

---

组合数学

不可重组合数学（留坑）

• $C^n_m$表示在$m$中选$n$个的方案数。（把$m$个无区别物品放到$n$个有区别篮子的方案数)
  $C^m_n=\frac{n!}{m!(n-m)!}$
  $C^m_n=C_{n-1}^{m-1}+C^m_{n-1}$
  $C^k_n=C^{n-k}_n$
  $C^{k+1}_n=C^k_n*\frac{n-k}{k+1}$
  $$(a+b)^n=\sum^n_{k=0}C_n^k a^{n-k} b^k$$
• $P^n_m$表示在$m$中选$n$个的排列数。（把$m$个有区别物品放到$n$个有区别篮子的方案数）
  $P_m^n=C_m^n*n!$
• $S^n_m$表示斯特林数。（把$m$个有区别物品放到$n$个无区别篮子，且篮子不空的方案数）
  $S_m^n=S_m^{n-1}*m+S_{m-1}^{n-1}$
  $S_m^n=0(m>n)$

可重组合数学

可重排列

有$k$个元素，其中第$i$个元素有$n_i$个，求全排列数。
$P'=\frac{(\sum_{i=1}^k n_i)!}{n_i!n_2!...n_k!}$
即先全排列，然后给每个元素编号。

可重组合

有$k$个元素，每个元素可选无穷多个,一共选$k$个，求方案数。
$C'=C_{k-n+1}^{n-1}=C_{k-n+1}^k$
假如第$i$个元素选$x_i$个，那么原问题变为$x_1+x_2+...+x_n=k$。
令$y_i=x_i+1$,那么$y_1+y_2+y_3+...+y_n=k+n$
此时$y>0$,即每个元素都要选。所以等于在$k+n$个元素($k+n-1$个空位)间放$n-1$个隔板。

卡特兰数

前几个数：$1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 1767263190$
好像我只会用它打表找规律
公式:
$C'[n]=\frac{C_{2n}^n}{n+1}$
$C'[n]=\sum_{i=1}^{n-1} C'^iC'^{n-i}$
应用：

• 一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?
• n个节点构成的二叉树，共有多少种情形？
• 求一个凸多边形区域划分成三角形区域的方法数？
• 在圆上选择2n个点，将这些点成对链接起来使得所得到的n条线段不相交，一共有多少种方法？
• n*n的方格地图中，从一个角到另外一个角，不跨越对角线的路径数.
• n层的阶梯切割为n个矩形的切法数。

数论分块

求解$\sum_{i+1}^n\lfloor\frac{n}{i}\rfloor$
据观察，$\lfloor\frac{n}{i}\rfloor$的取值只有$\sqrt{n}$个。
定理：若有一个值$i$，那么数论分块中其同值上界为$ceil=\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor$。
即在$[i,ceil]$这一段区间内，$\lfloor\frac{n}{i}\rfloor$的取值是一样的，于是可计算整块贡献。

int l = 1 , r , ans = 0;
while(l<=n){
    r = n/(n/l);    
    ans += (r-l+1)*(n/i);
    l = r + 1;
}

---

莫比乌斯反演

莫比乌斯反演有两种形式。。。

第一种

如果我们有函数$f(x)$,以及$g(x)$，并且有

$$g(x)=\sum_{d\mid x}f(d)$$
那么，我们就有
$$f(x)=\sum_{d\mid x}\mu (\frac{x}{d})g(d)$$

第二种

如果我们有函数$f(x)$,以及$g(x)$,并且有：

$$g(x)=\sum^n_{x\mid d}f(d)$$
其中$n$是我们限定的一个范围
那么我们可以得到：
$$f(x)=\sum_{x\mid d}^n\mu(\frac{d}{x})g(d)$$

至于$\mu$函数，叫做莫比乌斯函数。
其定义为：

$$\sum_{d\mid x}\mu(d)=[x==1]$$
性质？
$\mu(1)=1$,而往后面的所有$\mu(x)(x>1)$都有
$$\mu(x)=-\sum_{d\mid x 且 d\neq x}\mu(d)$$
或者是

• $x=p_1p_2...p_n$时，$\mu(x)=(-1)^n$
• $x=p^2d$,此时$\mu(x)=0$
• $x=1$时$\mu(x)=0$
  至于运用？留个坑，以后写总结吧。