扩展欧几里得

求 ax+by=gcd(a,b) 的一组可行解（必有）
\begin{cases} ax_1+by_1=gcd(a,b)\\ bx_2+(a\ mod\ b)y2 = gcd(a,a\ mod\ b) \end{cases}
\because gcd(a,a\ mod\ b)=gcd(a,b) \quad\therefore ax_1+by_1=bx_2+(a\ mod\ b)y2
\because a\ mod\ b=a-(b\times\lfloor\frac{a}{b}\rfloor)
\therefore ax_1+by_1=ay_2+b(x_2-\lfloor\frac{a}{b}\rfloor y_2)
\therefore x_1=y_2, y_1=x_2-\lfloor\frac{a}{b}\rfloor y_2
扩展欧几里得算法求出的可行解必有 |x|\leq b, |y| \leq a

矩阵板子

int exgcd(int a, int b, int &x, int &y) {
  int x1 = 1, x2 = 0, x3 = 0, x4 = 1;
  while (b != 0) {
    int c = a / b;
    std::tie(x1, x2, x3, x4, a, b) =
        std::make_tuple(x3, x4, x1 - x3 * c, x2 - x4 * c, b, a - b * c);
  }
  x = x1, y = x2;
  return a;
}

普通板子（貌似好记一点？）

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

求解不定方程

对于
ax+by=m之类的式子，我们可以由扩展欧几里得写出相同形式的式子
ax'_1+by'_1=gcd(a,b)
因为求整数解，所以只有当 m\bmod gcd(a,b)=0 时才有解
所以其中一个解即为 (x_1,y_1) = (x'_1\times m/ gcd(a,b),y'_1\times m/ gcd(a,b))
又因为 a(x_1-n*b)+b(y_1+n*a) = m
所以可知 x 的通解为 x_1-n*b=x'_1-b/gcd(a,b)*n
记 b_1=b/gcd(a,b)
x 的最小解为 (x'_1-k*b_1)\bmod b_1

除法分块

对于 \sum\limits_{i=1}^{N} \lfloor\frac{N}{i} \rfloor，在一定范围内 \lfloor\frac{N}{i} \rfloor 的值是不变的，所以可以使用等差数列求解
基于这一引理，我们可以推广到更普通的情况，当可以在 \Theta(1) 内计算出 f(r)-f(l) 时，就可以用分块来处理 \sum\limits_{i=1}^{N} f(i)g(\lfloor \frac{N}{i} \rfloor) 的问题

对于分块的每一个区间，他的左边界就是 l=r_{last}+1，右边界就是 \lfloor\frac{N}{\lfloor\frac{N}{l} \rfloor}\rfloor
粗略的复杂度为 \Theta(\sqrt{N})