我恨数论
扩展欧几里得
求 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})