数论

因数

欧几里得算法：
- 求$a,b$最大公因数$gcd(a,b)$
  太过简单，只给代码(llo为long\ long):
```
      llo gcd(llo a, llo b)
      { return b == 0 ? a : gcd(b, a % b); }
```
- 求$a,b$最小公倍数$lcm(a,b)$
  $$lcm(a,b)=\frac{a*b}{gcd(a,b)}$$

分解质因数

      int cnt = 0;
      for (int i = 2; 1ll * i * i <= x; i++) 
          if (x % i == 0) {
              p[++cnt] = i;
              t[cnt] = 0;
              while (x % i == 0) {++t[cnt]; x /= i;}
          }
      if (x > 1) {++cnt; p[cnt] = x; t[cnt] = 1;}

从小到大枚举，对于任意质数，直接进行代码所示的枚举而对于合数来说，它一定是由较小的质数组成，即使原$x$ % (这个数) $==$ $0$，但$x$经过前面的处理已经将这个组成这个合数的因子除掉了，自然当前$x$ % (这个数) $!=$ $0$

最小质因子：
- 求解方法：对筛法求素数代码进行改变
- 代码：
```
      memset(sf, true, sizeof(sf));
      memset(mindiv, 0, sizeof(mindiv));
      n = 1000000;
      for (int i = 2; i <= n; i++) {
          if (!f[i]) continue;
          mindiv[i] = i;
          for (int j = i + i; j <= n; j += i) {
              f[j] = false;
              if (!mindiv[j]) mindiv[j] = i;
          }
      }
```
  对于每个数，由于是从小向大枚举，则它的最小质因子一定是最先能够筛掉它的数
- 利用最小质因子求出所有质因子：
  设$minx$为$x$的最小质因子，则显然$x = (x / minx) × minx$，设$miny$为$(x / minx)$的最小质因子，又有$(x / minx) = (x / minx / miny) × miny$这样递归下去即可求出$x$的所有质因子
- $2$ ~ $n$每个数的质因子个数
  $$f[1] = 0, f[x] = f[x / mindivx] + 1$$
- $2$ ~ $n$每个数的不同质因子个数
  $$f[1] = 0,f[x] = f[x / mindivx] + mindivx \mod (x / mindivx) ? 0 : 1$$

快速求$1$~$n$所有数的因子：

$1$~$n$的因子总数为$nlogn$ $(n / 1 + n / 2 + n / 3 + n / 4 + …… n / n)$

代码：

      vector <int> div[N];
      for (int i = 1; i <= n; i++) {
          div[i].push_back(i);
          for (int j = i << 1; j <= n; j += i)
              div[j].push_back(i);
      }

类似于筛法思想，将当前数的所有倍数添加当前数为因子，时间空间都是$O(nlogn)$的

精确的求某一个数的所有因子：质因数分解 $+$ 指数搜索

例：$100 = 2^2 × 5^2$
因子：$2^0 × 5^0, 2^1 × 5^0……$

质数

线性筛：

      int cnt = 0;
      memset(sf, true, sizeof(sf));
      for (int i = 1; i <= n; i ++) {
          if (sf[i]) prime[++cnt] = i;
          for (int j = 1; j <= cnt; j++) {
              if (i * prime[j] > n) break;
              sf[i * prime[j]] = false;
              if (i % prime[j] == 0) break;
          }
      } sf[1] = sf[0] = false;

对于一个数，只要有一个质数将它筛去即可确定是合数，所以对于每个数$x$，将当前素数表里不大于$mindivx$的数与$x$的乘积筛掉，而大于$mindivx$的质数与$x$的乘积必定会在之后被大于x的数筛掉，减小了筛的次数，达到线性的复杂度 $(注意两个break的次序和位置)$，适用于$n > 1e7$的数据范围

一些我不知道怎么分类但是非常强大的算法

扩展欧几里得算法$(exgcd)$：
- ~~我自闭了~~
- 对扩欧的理解：
  
  给出不定方程,形如
  
  $$ax+by=c$$
  
  满足条件的整数解$x,y$有很多(废话)，当且仅当$gcd(a,b)|c$时方程有整数解
  
  证明：
  方程两边同时除以$gcd(a,b)$
  
  $$\frac{a}{gcd(a,b)}* x+\frac{b}{gcd(a,b)}*y=\frac{c}{gcd(a,b)}$$
  
  观察等式，等式左边为一整数，故等式右边亦为一整数
  所以
  
  $$gcd(a,b)|c$$
  
  证毕
  
  因此，可以转化为求一组$x,y$，满足$ax+by=gcd(a,b)$，在求解原方程等式两边同时乘以$\frac{c}{gcd(a,b)}$即可
  对于求解$ax+by=gcd(a,b)$，可以找出一组$x0,y0$
  使
  $$ax_0+by_0=gcd(a,b)$$
  进而表达出通解公式：
  
  $$x=x_0+t*\frac{b}{gcd(a,b)}$$
  
  $$\qquad \qquad \quad y=y_0-t*\frac{a}{gcd(a,b)},\quad\forall t\in Z$$
  
  推导过程：
  $$ax_0 + by_0$$
  $$=ax_0+\frac{a* b}{gcd(a,b)}+by_0-\frac{b* a}{gcd(a,b)}$$
  $$=a(x_0+\frac{b}{gcd(a,b)})+b(y_0-\frac{a}{gcd(a,b)})$$
  $$ax+by=a(x_0+t* \frac{b}{gcd(a,b)})+b(y_0-t* \frac{a}{gcd(a,b)}),\quad \forall t\in Z$$
  因此，若要表达其它满足方程的$x,y$
  $$x=x_0+t* \frac{b}{gcd(a,b)}$$
  $$\qquad \qquad \quad y=y_0-t*\frac{a}{gcd(a,b)},\quad\forall t\in Z$$
  推毕
  
  那么只需要求出一组特解$x_0,y_0$就好了，而求解特解，便是扩欧算法的核心所在
  代码(~~因为怂~~都开了$long\ long$)：
```
  llo exgcd(llo a, llo b, llo &x, llo y) {
      if (!b) {x = 1, y = 0; return a;}
      llo gcd = exgcd(b, a%b, x, y);
      llo z = x, x = y, y = z - y * (a / b);
      return gcd;
  }
```
  解释：
  在欧几里得算法中，每一个状态$a,b$的下一个状态是$b,a\mod b$
  假设当前状态的下一个状态中已经求解出一组$x_1,y_1$
  $$b* x_1+a\mod b* y_1=gcd(a,b)$$
  因为
  $$a\mod b=a-(a/b)* b$$
  所以
  $$b* x_1+(a-(a/ b)* b)* y1=gcd(a,b)$$
  $$b* x_1-(a/b)* b* y_1+a* y_1=gcd(a,b)$$
  $$a* y_1+b[x_1-(a/b)* y_1]=gcd(a,b)$$
  那么在递归返回时可令
  $$x=y1,y=x_1-(a/b)* y_1$$
  欧几里得算法停止的状态，$b=0$，此时时$a$即为$gcd(a,b)$ 若使$a$的系数为$1$那么$b$的系数y便无关紧要了
  $$1* gcd(a,b)+k* 0=gcd(a,b)$$
  所以
  $$if(!b),x=1,y=k\quad \forall k\in Z$$
  为了方便使$y=0$
  注意：$x,y$是传址调用，否则无法起到递归返回时修改的目的
  
  $exgcd$算法的流程便结束了
- exgcd的应用：
  - 求最小整数解：
    
    回顾原方程：
    $$ax+by=gcd(a,b)$$
    $x$的最小整数解$min_x=x\mod \frac{b}{gcd(a,b)}$
    
    推导：
    假设$exgcd$求出原方程的一组解为$x_0,y_0$
    由于解集之间可以相互转化
    $$x_0=min_x+t*\frac{b}{gcd(a,b)}$$
    要求解$min_x$只需要$x_0\mod \frac{b}{gcd(a,b)}$即可
  - 求解$a$在$mod\ p$意义下的逆元(a^{-1})：
    
    逆元：
    对于一个实数$a$，如果存在一个$x$使得 $ax=1$，我们就把这个$x$叫做$a$的逆元，记做$x=a^{-1}$
    在一般数学中，我们所说的逆元就是倒数。
    在数论中，如果数字$a$存在一个对$p$的逆元$x$，可以写成$ax\equiv 1\ (mod\ p)$，$gcd(a,p)=1$，否则不存在逆元
    
    设$a^{-1}$为$x$，原式转化为
    $$ax\equiv 1\ (mod\ p)$$
    进而转化为
    $$ax+py=1$$
    $exgcd$解决
    
    代码(exgcd求解出的x是负数，return时需要处理)：
```
  llo inv(int a, int p) {
      llo x, y; exgcd(a, p, x, y);
      return (x % p + p) % p;
  }  
```
  - 线性同余方程：
    
    一般形式
    $$ax\equiv b\ (mod\ p)$$
    对此一定有$b<p$，而$b>p$时可先对$b$取模，等效
    式子可转化
    $$ax-kp=b$$
    $exgcd$求解
- 例题：
  - $luogu\ p1082$ 同余方程：模板题
  - $luogu\ p1516$ 青蛙的约会：先列出式子，套$exgcd$

费马小定理：
- 定义：若$p$为一质数，则$a^{p-1}\equiv 1\ (mod\ p)$
- 费马小定理求逆元：
  
  由定义上式可转化为
  $$a*a^{p-2}\equiv 1\ (mod\ p)$$
  因此$a^{p-2}$即为$a$在$mod\ p$意义下的逆元
  可以直接用快速幂求解