数论
扩展欧几里得(\(exgcd\))
用于求解不定方程\(ax+by=k\)且\(gcd(a, b)|k\)的解。
令\(ax+by=gcd(a,b)\)。求\(k\)的话只需要将\(x,y\)乘上\(\dfrac{k}{gcd(a,b)}\)。
\[gcd(a, b) = gcd(b, a\%b) \]\[ax_1+by_1=bx_2+(a-\lfloor \dfrac{a}{b}\rfloor \times b)y_2 \]\[ax_1+by_1=bx_2+ay_2-\lfloor \dfrac{a}{b}\rfloor by_2 \]\[ax_1+by_1=ay_2+b(x_2-\lfloor \dfrac{a}{b}\rfloor y_2) \]\[\begin{cases}x_{1}=y_{2}\\ y_{1}=x_{2}-\lfloor \dfrac{a}{b}\rfloor y_{2}\end{cases}\]void exgcd(int a, int b, int &x, int &y){
if(!b){x = 1, y = 0; return;}
exgcd(b, a % b, x, y);
int p = x;
x = y, y = p - (a / b) * y;
return;
}
然后解得一组解\(x_1, y_1\)，则有
\[ax_1+by_1=gcd(a,b) \]\[d \in Q那么a(x_1+db)+b(y_1-da)=gcd(a,b) \]于是我们就有了新解\(x_2=(x_1+db),y_2=(y_1-da)\)。
整除分块
用于快速计算一些含有除法向下取整的和式（即形如$\sum ^{n}_{i=1}f\left( i\right) g( \lfloor \dfrac{n}{i} \rfloor) \(）。时间复杂度\)O(\sqrt{n})$。
我们考虑将数\(1\sim n\)的数\(x\)按照\(\lfloor \dfrac{n}{x} \rfloor\)的值分块。
对于\(l\)所在块的最右端\(r, r=\left\lfloor \dfrac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor\)。
\(\left\lfloor\dfrac{n}{l}\right\rfloor\)表示能将\(n\)最多分为多少个长为\(l\)的块。
\(\left\lfloor \dfrac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor\)表示能将\(n\)分为\(\left\lfloor\dfrac{n}{l}\right\rfloor\)个块的最长长度。
int l = 1, r;
while(l <= n){
r = x / (x / l);
l = r + 1;
}
数论函数：
定义域是正整数的函数。
狄利克雷卷积：
\[h\left( x\right) =\sum _{ d| x}f\left( d\right) g\left( \dfrac{x}{d}\right) =\sum _{ab=x}f\left( a\right) g\left( b\right) \]积性函数：
若函数\(f(n)\)满足\(f(1)=1\)且 \(\forall x,y\in\mathbf{N}^*,~(x,y)=1\) 都有 \(f(xy)=f(x)f(y)\)，则\(f(n)\)为 积性函数。
若函数\(f(n)\)满足\(f(1)=1\)且 \(\forall x,y\in\mathbf{N}^*\) 都有 \(f(xy)=f(x)f(y)\)，则 \(f(n)\) 为 完全积性函数。
一些定义：
单位函数：
\(\varepsilon(n)=[n=1]\)。（完全积性）
恒等函数：
\(\operatorname{id}_k(n)=n^k，\operatorname{id}_{1}(n)\) 通常简记作 \(\operatorname{id}(n)\)。（完全积性）
常数函数：
\(1(n)=1\)。（完全积性）
除数函数：
\(\sigma_{k}(n)=\sum_{d\mid n}d^{k}\)。\(\sigma_{0}(n)\) 通常简记作 \(d(n)\) 或 \(\tau(n)\)，\(\sigma_{1}(n)\) 通常简记作 \(\sigma(n)\)。
欧拉函数：
\(\varphi(n)=\sum_{i=1}^n[(i,n)=1]\)
莫比乌斯函数：
\(\mu(n)=\begin{cases}1&n=1\\0&\exists d>1,d^{2}\mid n\\(-1)^{\omega(n)}&\text{otherwise}\end{cases}\)
其中 \(\omega(n)\) 表示 \(n\) 的本质不同质因子个数，它是一个加性函数。
重要性质：
\[\varphi \ast 1=id \]\[id\ast \mu =\varphi \]\[\sum_{d\mid n}\mu(d)= \begin{cases} 1&n=1\\ 0&n\neq 1\\ \end{cases}\]即 \(\sum_{d\mid n}\mu(d)=\varepsilon(n)，\mu * 1 =\varepsilon\)
常用转换：
\[\displaystyle [\gcd(i,j)=1]=\sum_{d\mid\gcd(i,j)}\mu(d) \]mu[1] = 1;
for(int i = 2; i < N; i++){
if(!vis[i]) mu[i] = -1, p[++tot] = i;
for(int j = 1; j <= tot && i * p[j] < N; j++){
vis[i * p[j]] = 1;
mu[i * p[j]] = -mu[i];
if(i % p[j] == 0){
mu[i * p[j]] = 0;
break;
}
}
}