？？？
注意：以下讨论的数若未特殊注明均为自然数。
1.1 欧几里得算法
引理：\(\gcd (a,b)=\gcd(b,a\bmod b)\)。特别地：当 \(b=0\) 时，\(\gcd(a,b)=a\)。
递归求解代码：
int gcd(int a,int b){return !b ? a : gcd(b,a % b);}
对于最小公倍数，有 \(\operatorname{lcm}(a,b)=\dfrac{a\times b}{\gcd(a,b)}\)。
1.2 扩展欧几里得算法
裴蜀定理
设 \(a,b\) 是不全为 \(0\) 的整数，对于任意整数 \(x,y\)，有 \(\gcd(a,b)\mid ax+by\)，且存在整数 \(x,y\)，使得 \(ax+by=\gcd(a,b)\)。
通过裴蜀定理能判断二元一次不定方程的解的存在性。
求解方程 \(ax+by=\gcd(a,b)\)
当 \(b=0\) 时，\(\begin{cases}x=1\\y=0 \end{cases}\) 为一组可行解；
否则由 1.1 引理转求解方程 \(bx'+(a\bmod b)y'=\gcd(b,a\bmod b)=\gcd(a,b)\)。
进一步推导：\(bx'+(a-\lfloor\dfrac{a}{b}\rfloor b)y'=ay'+b(x'-\lfloor\dfrac{a}{b}\rfloor y')\)，即通过 \(x',y'\) 能够得到一组原方程的解。
实现代码：
void exgcd(int a,int b,int &x,int &y){
if(!b)return x = 1,y = 0,void();
exgcd(b,a % b,y,x),y -= a / b * x;
}
一些等价问题
-
二元一次不定方程的整数解：\(ax+by=c\)
有解的充要条件为：\(\gcd(a,b)\mid c\)；
若方程存在一组解 \(\begin{cases}x=p\\y=q\end{cases}\)，则方程的通解为 \(\begin{cases}x=p+k\dfrac{b}{\gcd(a,b)}\\y=q-k\dfrac{a}{\gcd(a,b)}\end{cases}\)，其中 \(k\) 为任意整数。
-
同余方程：\(ax\equiv c\pmod b\)
可以化为：\(ax+by=c\)，转化为问题 1。
特殊地，当 \(c=1\) 时，求得的 \(x\) 为 \(a\) 在模 \(b\) 意义下的乘法逆元。
1.3 中国剩余定理
求解同余方程
其中，\(b_{1\sim n}\) 两两互质。
\(x\) 的通解形式为：\(x=\sum\limits_{i=1}^{n}m_im_i^{-1}c_i+kM\)。其中，\(M=\prod\limits_{i=1}^{n}b_i\)，\(m_i=\dfrac{M}{b_i}\)，\(m_i^{-1}\) 为 \(m_i\) 在模 \(b_i\) 意义下的乘法逆元，\(k\in \mathbb Z\)。
2023.11.17 错误：\(m_i\) 不能对 \(a_i\) 取模。但并不是因求乘法逆元产生的问题。
整数除法相关
\(\lceil a\rceil\)\(\lfloor a\rfloor\)
计算
整型计算除法为向零取整。将除数转为正数后再讨论结果的正负进行计算。
int cl(int a,int b){
if(b < 0)a = -a,b = -b;
return a >= 0 ? (a + b - 1) / b : a / b;
}
int fl(int a,int b){
if(b < 0)a = -a,b = -b;
return a >= 0 ? a / b : (a - b + 1) / b;
}
整除分块
复杂度 \(\mathcal O(\sqrt n)\)。似乎有两倍常数。开数组存储端点时需要注意。
for(int l = 1,r = 0;l <= n;l = r + 1){
r = n / (n / l);
//caculate
}
不等式
以下讨论均为整数。
\(ax\le b\Rightarrow x\le\lfloor\dfrac{b}{a}\rfloor\)
\(ax\ge b\Rightarrow x\ge \lceil\dfrac{b}{a}\rceil\)
\(ax< b\Rightarrow ax\le b-1\Rightarrow x\le \lfloor\dfrac{b-1}{a}\rfloor\)
\(ax>b\Rightarrow ax\ge b+1\Rightarrow x\ge \lceil\dfrac{b+1}{a}\rceil=\lfloor\dfrac{b}{a}\rfloor+1\)
拓展：给定限制 \(b\)，求满足相关条件的 \(a\) 的倍数。根据上述不等式，等价于求出 \(ax\) 的值。