KeBlog

O(1)黑科技

发表于 2019-10-10 更新于 2019-12-06 分类于算法

@CYJian 出了一道黑科技二合一，我就顺便跟着学了学。

O(1) gcd

在 O(V) 的预处理后可以做到 O(1) 查询 gcd ，其中 V 是权值的大小。

主要利用到的一个性质是可以将任意 x 分解为三个数 a * b * c ， a, b, c 分别满足以下两个条件之一：

不超过 $\sqrt{x}$ 。
是质数。

update: 之前写假了，感谢 @CYJian 的 hack 。

zzq 把满足这个性质的分解称为“迷之分解”，那我也这么叫吧。

考虑证明一下，顺便构造一个“迷之分解”。

找到 x 的最小质因子 p ，然后假设已知 x / p 的“迷之分解” A, B, C (A <= B <= C) 。
那么把 p 乘到 A 上就可以得到 x 的“迷之分解” A * p, B, C 。
分类讨论，如果 p 不超过 $\sqrt[4]{x}$ ，由于 A 是 A, B, C 三者中最小的，
一定满足 A 不超过 $\sqrt[3]{x/p}$ ，那么可得：

\[A \cdot p \leq \sqrt[3]{x/p} \cdot p = \sqrt[3]{xp^2} \leq \sqrt{x}\]

而如果 p 超过 $\sqrt[4]{x}$ ，由于 p 是最小质因子，
那么如果 x 的“迷之分解”有合数 C ， C 至少是 $p^2$ ，超过 $\sqrt{x}$ ，
那么 B 的大小就会比 p 小，与 p 是最小质因子矛盾，
因而此时 x 的“迷之分解”全是质数。

“迷之分解”的分析就是这样，通过线性筛可以很好预处理出 O(V) 内的所有数的“迷之分解”。
只需筛出每个数的最小质因子即可按上述方法递推出“迷之分解”。
然后只需预处理出 $O(\sqrt{V})$ 内两两的 gcd ，为了不带 log ，需要递推预处理。
此时求 gcd(x, y) 只需对于 x 的“迷之分解” A, B, C 依次对 y 求 gcd （每次求 gcd 后把 y 除以该 gcd ），
以 A 为例，如果 A 不超过 $\sqrt{x}$ ，直接查表可以得到 gcd(A, y) （查的是 gcd(A mod y, A) ），
否则 A 为质数，简单讨论一下就可以得到 gcd(A, y) 了。

关键部分参考实现：

int magic[maxv][3]; // 每个数的“迷之分解”
int gcd[maxb][maxb]; // 预处理的 gcd
int GCD(int x, int y) {
	int res = 1;
	for(int i = 0; i < 3; i ++) {
		int X = magic[x][i];
		int d;
		if(X < maxb)
			d = gcd[X][y % X];
		else if(y % X)
			d = 1;
		else
			d = X;
		res *= d;
		y /= d;
	}
	return res;
}

O(1) 快速幂

在 $O(\sqrt{p})$ 的预处理后可以做到对于一个固定的底数 O(1) 查询快速幂，
其中 p 是模数（或者上式是 $\sqrt{\phi(p)}$ ），或者是指数的范围。

这个就简单得多，对于每个 $a^k$ 的指数 k 都可以表示为 $a \sqrt{p} + b$ 的形式，
满足 $a, b < \sqrt{p}$ ，分别预处理即可，
即预处理 $a^0, a^1, a^2 ... a^{\sqrt{p}}, a^{2\sqrt{p}}, a^{3\sqrt{p}} ... a^p$ 。

整体二分

发表于 2019-10-10 更新于 2020-05-19 分类于算法

不久前学了整体二分，做了几道题，还在考试上派上用场过几次。
觉得自己大概懂了整体二分，直到一次碰上了强制在线的毒瘤题。。。

~~整体二分：从离线到强制在线~~

基础

大概讲讲整体二分吧。

整体二分大概用于这样一个场景：
有多组询问，每个询问可以二分，但是每个询问二分的时间不能接受，
而不同询问的二分有共同点，这时就可以用整体二分把多个询问一起二分。
所以这是个离线算法。

阅读全文 »

整除分块

发表于 2019-10-10 更新于 2020-07-26 分类于算法

（以下的除号皆表示整除）

用数论函数计算的时候，总会遇到这样一种问题： $\sum_{i=1}^n f(\frac{n}{i})$ 。 $O(n)$ 求往往无法满足需要。

但是打表可以发现， n/i 的取值对于一段连续的 i 是一致的，那么可以考虑一块一块求。

设已知当前块的左端点为 l ，如果知道右端点 r（左闭右开），意味着 $\forall l<=i<r, \frac{n}{i} = \frac{n}{l}$ ，这一块对答案的贡献就是 $(r-l) \times f(\frac{n}{l})$ 。

结论是 $r = n / (n / l) + 1$ 。

证明：

对于 l 设 $n / l = x$
那么由 $n \bmod l = n - n / l \cdot l = n - l \cdot x$ 可知 $ n - l x $
那么若 $l + 1$ 满足 $n / (l + 1) = n / l$ ，可知也有 $n - (l + 1) \cdot x \geq 0$
即 $n - l \cdot x \geq x$
对于 k 若 $n / k = n / l$ 而 $n / (k + 1) != n / l$
那么根据上式可得 k 满足 $ 0 n - k x < x$
所以 $n - k \cdot x = n \bmod x = n - n / x \cdot x$
所以 $k = n / x = n / (n / l)$
由 k 的定义 $n / k = n / l \& n / (k + 1) != n / l$ 可知 k+1 即是要求的 r

那么可以枚举块，当前 l,r 可以求得，下一个块的 l 显然是当前 r。

有时候会有点变化：

要求 $\sum_{i=1}^{min(n, m)} f(\frac{n}{i}) \cdot f(\frac{m}{i})$ 。

还是会存在 $\forall l \le i < r, \frac{n}{i} = \frac{n}{l} \& \frac{m}{i} = \frac{m}{l}$ 。

所以这样的区间的右端点为：$r = min(n / (n / l), m / (m / l)) + 1$ 。

所以还是可以一块一块的枚举求和。

类欧几里得

发表于 2019-10-10 更新于 2020-07-19 分类于算法

这里只是类欧几里得的一种：
快速求下式： \[f(a, b, c, n) = \sum_{i=0}^n \lfloor \frac{ai+b}{c} \rfloor\]

其中 a, b, c, n 都是正整数。

缩小 a, b 规模

首先的目标是让 a, b 小于 c 。

结论 1 ：
\[\lfloor \frac{Ax+B}{y} \rfloor = \lfloor \frac{A(x\%y)+B}{y} \rfloor + A\lfloor \frac{x}{y} \rfloor\]

证明：
首先用到整除与取模的转换： $\lfloor \frac{x}{y} \rfloor = \frac{x-x\%y}{y}$ 。
得到原命题等价于：
\[\frac{Ax+B-(Ax+B)\%y}{y} = \frac{A(x\%y)+B-(Ax+B)\%y}{y} + A\frac{x-x\%y}{y}\] \[Ax + B - (Ax+B)\%y = A(x\%y) + B - (Ax+B)\%y + A(x-x\%y)\] \[Ax - (Ax+B)\%y = A(x\%y) - (Ax+B)\%y + A(x-x\%y)\] \[Ax = A(x\%y) + A(x-x\%y)\] \[Ax = A(x\%y) + Ax - A(x\%y)\]
得证。

那么通过这个结论可以得知：
\[ \begin{equation} \begin{aligned} f(a, b, c, n) &= \sum_{i=0}^n \lfloor \frac{ai+b}{c} \rfloor \\\\ &= \sum_{i=0}^n (\lfloor \frac{(a\%c)i+b\%c}{c} \rfloor + i\lfloor \frac{a}{c} \rfloor + \lfloor \frac{b}{c} \rfloor) \\\\ &= f(a\%c, b\%c, c, n) + \sum_{i=0}^n ( i\lfloor \frac{a}{c} \rfloor + \lfloor \frac{b}{c} \rfloor) \\\\ \end{aligned} \end{equation} \]

后面那一段就是一个等差数列求和，于是 a, b 被转换为小于 c 。

转换成子问题减小规模

整除除了用取模代替外，还有一种方法。

结论 2 ：
\[\lfloor \frac{x}{y} \rfloor = \sum_{i=1}^{MAX} [i \leq \frac{x}{y}]\]
其中 MAX 是任意一个足够大的值。
证明？相当于从 1 开始数，感性理解即可。

那么通过这个结论可以得知：
\[ \begin{equation} \begin{aligned} f(a, b, c, n) &= \sum_{i=0}^n \lfloor \frac{ai+b}{c} \rfloor \\\\ &= \sum_{i=0}^n \sum_{j=1}^{(an+b)/c} [j \leq \frac{ai+b}{c}] \\\\ &= \sum_{i=0}^n \sum_{j=0}^{(an+b)/c-1} [j + 1 \leq \frac{ai+b}{c}] \\\\ &= \sum_{i=0}^n \sum_{j=0}^{(an+b)/c-1} [cj + c \leq ai+b] \\\\ &= \sum_{i=0}^n \sum_{j=0}^{(an+b)/c-1} [cj + c - 1 < ai+b] \\\\ &= \sum_{i=0}^n \sum_{j=0}^{(an+b)/c-1} [\frac{cj+c-b-1}{a} < i] \\\\ &= \sum_{j=0}^{(an+b)/c-1} \sum_{i=0}^n [\frac{cj+c-b-1}{a} < i] \\\\ &= \sum_{j=0}^{(an+b)/c-1} (n + 1 - \sum_{i=0}^n [i \leq \frac{cj+c-b-1}{a}]) \\\\ &= \sum_{j=0}^{(an+b)/c-1} (n - \lfloor \frac{cj+c-b-1}{a} \rfloor) \\\\ &= n \lfloor \frac{an+b}{c} \rfloor - \sum_{j=0}^{(an+b)/c-1} (\lfloor \frac{cj+c-b-1}{a} \rfloor) \\\\ &= n \lfloor \frac{an+b}{c} \rfloor - f(c, c-b-1, a, (an+b)/c-1) \end{aligned} \end{equation} \]

那么就得到了一个递归计算 f(a, b, c, n) 的算法，
a = 0 时上式不成立，因为上面的推导有除以 a 的步骤。
因此将 a = 0 作为终止状态，此时 f 的计算是常数数列求和。
复杂度是对数复杂度 log(a)，因为上面的过程规模的减小速度相当于 gcd 。

数形结合

复习的时候看到这么多式子头都大了，但是这个类欧事实上就是数一个三角形内的整点数，第一步很好理解，第二步本质上就是把坐标轴翻转了一下然后用一个正方形的点数减去一个三角形的点数（事实上可以不用这个补集转换），很快就可以得到同样的结论，可以避免冗长的纯式子推导。

放在二维平面上，第一步的本质就是把斜率固定在小于 1 的数，第二步的本质就是翻转坐标轴，翻转后斜率会变为原来的倒数，于是会超过 1 。这样反复进行就可以逐渐数完三角形内的所有整点。

UPD: 准确来说不是三角形，是梯形，但显然两者可以相互转换。

但是更复杂的类欧这个数形结合好像就不管用了，还是得用数学推导。

线段树分治

发表于 2019-10-10 更新于 2019-12-06 分类于算法

作用

线段树通过维护序列，可以维护一个承载各种操作的时间轴。

通常用于辅助一些不支持删除操作的数据结构（线性基，并查集），
这种情况可以用线段树分治维护操作影响的时间来巧妙地避开删除。

线段树结构

线段树分治用到的线段树（以下简称线段树）是以询问的时间为键值，
没有权值只有标记的线段树。

也就是线段树的一段区间对应的是一段询问（一段时间）。

这样的线段树只需要支持区间修改（打标记）。
每一个操作都会影响一段时间，对应于线段树的区间修改。

例题

这玩意需要一个例题才讲的清。
（由于线段树分治用于辅助其他数据结构，再看例题前得先会线性基）

维护一个集合，每次操作可以加入一个数或删除一个已经存在与集合的数。
每次操作后要回答这个集合的最大异或和。
操作次数 1e5 。

暴力线性基

如果只有插入没有删除，这题就是一遍线性基。

但是不巧线性基不支持删除，所以只能在每次删除后重构线性基。
复杂度平方带对数，稳 T 。

时间轴

将每次操作看做时间点，假设数 x 在时刻 l 被插入， r 被删除，
那么 x 只存在于 [l, r) 这段时间，
假如每个时刻开一个线性基，那么将 x 插入 [l, r) 的每个线性基，
这样就可以在最后通过线性基询问得到每个时刻的答案，
复杂度还是平方带对数，稳 T 的离线算法。

线段树优化

比较上述两种算法，
第一种复杂度瓶颈在于重构线性基，实在是没有什么优化空间，
但是第二种算法中，复杂度瓶颈在于将 x 插入到 [l, r) 的每个线性基，
这个操作相当于一个区间修改，可以用线段树优化。

那么一个优秀的算法就出来了：
线段树每个节点维护一个 vector （相当于懒标记），插入 x 将直接加在线段树对应区间的 vector　内。
所有操作过后会得到一个只有懒标记的线段树，
然后考虑如何通过这样一颗线段树得出所有答案。

处理懒标记

懒标记下传？
不存在的，因为懒标记是一个 vector, 下传的复杂度并不是 O(1) ，
不难验证下传所有懒标记会使复杂度重回 n 方。

既然不能下传，那就进行 n 次单点查询？
一个道理，单点查询的复杂度并不是 log(n), 这样做同样对复杂度没有优化。

~~那就没救了~~

分治

线段树分治，不能只有线段树，还要分治啊。

现在需要只把每个懒标记访问一遍就得出所有答案。

dfs 整颗线段树（实际上就是分治），深度是 log 级别的，那么对每一个深度开一个线性基。
如能能让 dfs 每个节点时该深度线性基维护的是这个节点到根的所有懒标记，
最后 dfs 到每个叶子节点就可以得到该叶子节点到根的懒标记的线性基，也就可以求出这个叶子节点的答案。

假设当前 dfs 到 u, 深度为 d, 深度对应的线性基已经是维护其到根的懒标记。
dfs 到一个新点 v 一定会使深度 + 1 ，将当前深度 d 的线性基拷贝到下个深度 d + 1 中。
那么 dfs 到 v 后再将 v 的懒标记加到 d + 1 的线性基中，d + 1 的线性基也就满足了要求。
通过这样的过程就能够做到只访问每个懒标记一遍。

这就是线段树分治了。

真 - 例题

这两道题就没有这么裸了。

洛谷八纵八横（线段树分治 + 线性基）

BZOJ 二分图（线段树分治 + 并查集）

组合数公式

发表于 2019-10-10 更新于 2020-05-03 分类于算法

$ C_n^m $ 在组合数学中的意义：在 n 个元素选 m 个元素的方案数。

公式

公式 1

\[ C_n^m = \frac{n!}{m! * (n-m)!} \]

组合数的通项公式。

当要求组合数模一般模数时 ，通项公式的分母可能没有逆元导致不可行。

公式 2

\[ C_n^m = C_n^{n-m} \]

基本性质，可以由通项公式得出。

公式 3

\[ C_n^m * C_m^k = C_n^k * C_{n-k}^{m-k} \]

公式 4

\[ C_n^m = C_{n-1}^{m-1} + C_{n-1}^m \]

组合数的基本递推式。

当要求组合数模一般模数时 ，常用这种方法预处理组合数。

公式 5

\[ \sum_{i=0}^n C_n^i = 2^n \]

组合意义： n 个元素选任意元素的方案数。每个数都可以选或不选，所以方案数为 $ 2^n $ 。

同样可以由二项式定理： $ (x + 1)^n = _{i=0}^n C_n^i * x^i $ 得出。

公式 6

\[ \sum_{i=0}^n (C_n^i)^2 = C_{2n}^n \]

公式 7

\[ C_{n+m}^k = \sum_{i=0}^k C_n^i * C_m^{k-i} \]

从组合数学上的定义出发，在 n + m 个元素中选 k 个，相当于先在前 n 个元素中选 i 个再在后 m 个元素中选 k - i 个。枚举这个 i 把方案数相加就能得到最终方案数。

公式 8

\[ \sum_{i=0}^n C_{k+i}^k = C_{k+n+1}^n \]

进一步可以得到下式：

\[ \sum_{i=0}^n \sum_{j=0}^m C_{i+j}^i = C_{n+m+2}^{m+1} - 1 \]

类似的还有：

\[ \sum_{i=0}^n C_{i}^k = C_{n+1}^{k+1} \]

Lucas 定理

\[ C_n^m \% p = C_{n/p}^{m/p} * C_{n \% p}^{m \% p} \% p \]

常用于模数较小的组合数取模。

莫比乌斯反演

发表于 2019-10-10 更新于 2020-05-10 分类于算法

（以下除号皆表示整除）
对于一些式子复杂度大的数论题，或许用莫比乌斯反演可以高效解决问题。

前置技能：

基本数论函数
狄利克雷卷积

莫比乌斯函数满足 $\mu \times I = \epsilon$

即 $\sum_{d|n}\mu(d) = [n = 1]$

表达式为：

\[ n = 0 : \mu(n) = 1 \] \[ n = \prod_{p|n\,and\,p\,is\,prime} p : \mu(n)=(-1)^k \] \[ otherwise : \mu(n)=0 \]

证明：
~~暂时不会~~

莫比乌斯反演：
对于数论函数 $f(n)$ ，设 $F(n) = \sum_{d|n}f(d)$
即 $F = f \times I$
则有 $f(n) = \sum_{d|n}F(d)\cdot\mu(\frac{n}{d})$
即 $f = F \times \mu$

证明：

\[ \because \; F = f\cdot I \] \[ \therefore \; F\cdot \mu = f\cdot I\cdot \mu \] \[ \because \; I\cdot \mu = \epsilon \] \[ \therefore \; F\cdot \mu = f\cdot \epsilon \] \[ \therefore \; f = F\cdot \mu \]

莫比乌斯反演好像主要是用来推式子，F 比 f 好做的话，就可以试试莫比乌斯反演。

另外事实上只需要熟知 $\mu$ 函数的性质，直接推式子就行了，
绝大多数情况下（至少是我遇到的所有情况下）并不需要莫比乌斯反演。

另外莫比乌斯反演有个很简单的 $O(nlogn)$ 实现，不需要筛 $\mu$ ，直接按定义枚举每个数的倍数去筛即可。

FFT

发表于 2019-10-09 更新于 2019-12-06 分类于算法

前置知识

首先要知道关于多项式的一些知识。

其次要对复数有一些了解。

点值表示法

从多项式中，已经知道了多项式乘法的朴素算法时间复杂度为 $ O(n^2) $ 。原因在于多项式是用系数表示法定义的。

重新定义 n 次多项式 a 为满足 $ k (http://blog.miskcoo.com/2015/04/polynomial-multiplication-and-fast-fourier-transform) 。

迭代实现

上述过程用递归实现常数较大，因而有一个迭代实现 FFT 的快速版本。

蝴蝶操作

FFT 的每个值都是由子问题的两个值转化而来，且这两个值可以转换成两个需要的值（ FFT 复杂度的保证）。若用一个数组 a 表示多项式。那么蝴蝶操作形如：

complex Wn; // 单位根的幂
complex a0 = a[x], a1 = a[y];
a[x] = a0 + a1 * Wn;
a[y] = a1 + a0 * Wn;

这样取出了数组中两个值后再修改相应位置的两个值，就是蝴蝶操作。

Rader 排序

Rader 排序的目的是让表示多项式的数组可以进行蝴蝶操作。

盗图一张： luogu

摘自洛谷：

剩下的问题就是把初始的数组变成最后一层的样子了。
先别急着写一个递归函数暴力把位置换过去。
来观察一下最后序列的编号的二进制表示000, 100, 010, 110, 001, 101, 011, 111，
是不是与原来 000, 001, 010, 011, 100, 101, 110, 111 相比，
每个位置上的二进制位都反过来了？
这样的变化叫做 Rader 排序。

逆序对

发表于 2019-10-09 更新于 2019-12-06 分类于算法

在数列 a 中,逆序对即是满足 $i < j$ 且 $a_i > a_j$ 的数对。许多情况下你推式子推着推着就推出个 $\sum_{i=1}^n \sum_{j=i+1}^n a_i> a_j$，这就是逆序对的数量。

暴力

朴素的求法自然是 $O(n^2)$ 地枚举 $i, j$ 统计，这里不再赘述。

归并

前置技能：归并排序。

这应该是最主流的求逆序对的方法了。

要求一个区间内的逆序对数，假设已经递归求出两个子区间的逆序对数，接下来要做的就是求一个在左区间，一个在右区间的逆序对数。

考虑归并排序的过程，在两个指针比较大小时进行统计。

设左右区间的当前比较指针（下标）为 p1, p2, 当找到第一个 p2 使 $a_{p1}< a_{p2}$ 时，可知 $\forall i\in [p1max+1, p2),\;a_{p1}> a_{p2}$ 。那么横跨两个子区间的以 p1 为左端点的逆序对就有 p2-p1max-1 个。对所有 p1 统计和即可。

值得注意的是，p2>r（区间右端点）退出时，此时左区间未处理的数对答案都有 r-p1max 的贡献因为此时左区间剩下的数都比右区间所有数大。

复杂度 $O(n \cdot log_2n)$ 。

线段树/树状数组：

前置技能：线段树（或树状数组）。

以线段树为例。

做法 1

用线段树维护区间内有效数的个数。之所以是有效的数，是因为要从小到大删数。如果一个数 $a_i$ 是最小的，那么以其为右端点的逆序对就是 1 至 i-1 的数的个数。

接下来呢？在线段树中删掉最小的数（单点修改 -1），那么第二小的数 $a_j$ 在此时就是最小的数，同样有 1 至 j-1 的数的个数（区间查询）的贡献。以此类推从小到大一个个删数即可。

复杂度$O(n \cdot log_2n)$。

做法 2

离散化后用线段树维护一个桶。

从左到右依次计算每个数为右端点的逆序对并加入桶，即对每个数求该数左边比该数大的数的个数。设第 i 个数左边有 $f_i$ 个比 $a_i$ 大的数，那么 $f_i$ 的值即是当前线段树上 $a_i+1~a_{max}$ 的询问。

同样复杂度是 $O(n \cdot log_2n)$。

这种做法稍稍改变可以高效解决一种特殊的问题：

对于 01 串求串中 1 的数量比 0 的数量大的区间的数量。

比较容易想到的做法是将 0 看成 -1，区间中 1 比 0(-1) 多等价于区间和大于 0 。区间和可以转换为前缀和 s，那么 l,r 这一区间和大于 0 等价于 $s_r - s_{l-1} > 0 (r >= l)$。移项后即是 $s_r > s_{l-1} (r > l-1)$，所以题目可以转换为求前缀和的逆序对，复杂度 $O(n \cdot log_2n)$ 。

但是这个问题有特殊性，由 01 串的至可知相邻两个前缀和的差值一定是 1 ，利用这一个性质可以有更高效的方法。

用做法 2 求逆序对，从左到右依次扫，对于当前 $a_i$ 一定比 $a_{i-1}$ 大 1 或者小 1，利用到这个差值，比 $a_i$ 大的数相当于当前线段树 $a_i+1$ 到 $a_{max}$ 的询问，若 $a_i = a_{i-1}+1$ ，那么 $f_{i-1}$ 就是 $a_i$ 到 $a_{maxn}$ 的询问，否则就是 $a_i+2$ 到 $a_{max}$ 的询问。那么 $f_i$ 与 $f_{i-1}$ 的差只在 $a_i$ 或 $a_i+2$ 中，长度为一，完全没必要用线段树，用数组维护桶即可。

复杂度 $O(n)$。

数论函数玄学操作

发表于 2019-10-09 更新于 2020-06-14 分类于整理

数论函数推式子是真的玄学，乱七八糟的一脸懵逼，好不容易看懂了转身又 tm 忘了，这里列出一些我见过的。

持续更新。

update: 证明都删掉了，这是篇整理，目的是让结论更一目了然。~~需要证明联系我我免费讲解~~

常见数论函数卷积

\[ \mu \cdot I = \epsilon \]

\[ \phi \cdot I = id \]

\[ \mu \cdot id = \phi \]

\[ id \cdot I = \sigma \]

常见数论函数 f(ij) 化简

\[ d(i \cdot j) = \sum_{x|i} \sum_{y|j} [gcd(x, y) = 1] \]

\[ \sum_{d|ij} f(i \cdot j) = \sum_{x|i} \sum_{y|j} [gcd(x, y) = 1] f(\frac{iy}{x}) \]

\[ \phi(i \cdot j) = \phi(i) \phi(j) \frac{gcd(i, j)}{\phi(gcd(i, j))} \]

常见数论函数求和

\[ \sum_{i=1}^n d(i) = \sum_{i=1}^n \lfloor \frac{n}{i} \rfloor \]

互质条件转换

\[ [gcd(i, j) = 1] = \sum_{d|i,d|j} \mu(d) \]

\[ \sum_{i=1}^n \sum_{j=1}^m f(i, j) [gcd(i, j) = 1] = \sum_{d=1}^{min(n, m)} \mu(d) \sum_{i=1}^{n/d} \sum_{j=1}^{m/d} f(id, jd) \]