AtCoder
Mark Chen |
26 Jun 2021
报告错误
如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：
- 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
- 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库
题目翻译
题目中要求找到 $(x, y)$ 的数量使得 $L\leq x, y\leq R$ 且满足条件 $gcf(x, y) \neq 1$, $gcf(x, y) \neq x$ $gcf(x, y) \neq y$.
我们可以将上面的最后三个条件重新翻译一次：
- $gcf(x, y) \neq 1 \rightarrow x, y\text{ are not coprime }$
- $gcf(x, y) \neq x \rightarrow y \text{ is not the multiple of }x$
- $gcf(x, y)\neq y \rightarrow y > x$
时间复杂度初分析
这题的 $L, R$ 最大值是 $10^6$，所以一定不可能遍历所有的 $(x, y)$ 对。这样的时间复杂度是 $O(n^2)$，一定会 TLE 的。
既然遍历所有的 $(x, y)$ 是不可能实现的，我们有没有可能用一个数学公式直接计算出符合条件的数对数量呢？
数学分析
如果 $y$ 是 $x$ 的倍数则 $x, y$ 不可能互质。所以这题的结果可以用这个方式表达：
\[Result = AllPairs - CoprimePairs - MultPairs\]其中 $AllPairs - CoprimePairs$ 计算的是所有数对中不互质的数对数量。
计算不互质对的数量？
在具体计算之前，先让我们思考以下如果我们说 $x, y$ 不互质，实际上是什么意思。
\[gcd(x, y) = 1 \leftrightarrow x, y \text{ coprime} \leftrightarrow x=mk, y=nk, k\neq 1\]这三个表达式是等价的。
接下来，我们定义一些符号
| 符号 | 解释 |
|---|---|
| $\mathbb{K}$ | 集合 $\mathbb{K}$ 中的所有元素都有不超过1个相同的质因数。（ 例子：$2\in \mathbb{K}, 6\in\mathbb{K}, 4\notin \mathbb{K}$） |
| $\mathbb{K}_{odd}$ | $\mathbb{K_{odd}}\subset \mathbb{K}$，集合 $\mathbb{K}_{odd}$ 中所有的元素都只有奇数个质因数且属于 $\mathbb{K}$ |
| $\mathbb{K}_{even}$ | $\mathbb{K_{even}}\subset \mathbb{K}$，集合 $\mathbb{K}_{even}$ 中所有的元素都只有偶数个质因数且属于 $\mathbb{K}$ |
| $\mathbf{C}_n^m$ | 在 $n$ 个元素中选择 $m$ 个的所有组合情况数 |
引入两个引理
Lemma 1
\[\forall k\in\mathbb{K}_{even}, \exists k_1, k_2\in\mathbb{K}_{odd}\text{ such that } k=k_1k_2\]任意一个有偶数个质因数的 $k$ 值都可以用两个拥有奇数个质因数的 $k$ 值之积表示。
Lemma 2
\[\forall n\in \mathbb{Z} \wedge n\gt 1, \exists k \in \mathbb{K} \text{ such that } n=mk\]任意一个大于1的整数 $n$，总是存在一个 $k$ 值使得 $n$ 是 $k$ 的倍数
通过公式 $\lfloor\frac{R}{k}\rfloor - \lfloor\frac{L-1}{k}\rfloor$, 我们可以计算出区间 $[L, R]$ 中 $k$ 的倍数的数量，然后通过取所有 $k$ 倍数的组合数量来求出不互质的数对数量。然鹅，这样的计算方法有很大的问题：
想象以下数列，其中 $k_1, k_2\in \mathbb{K}_{odd}$
\[[L, \cdots, 2k_1, 5k_2, k_1k_2, 7k_2, \cdots, 2k_1k_2, \cdots, R]\]当计算所有 $k_1$ 在 $[L, R]$ 中的倍数时， $(k_1k_2, 2k_1k_2)$ 被计算了一次，当计算所有 $k_2$ 在 $[L, R]$ 中的倍数时，$(k_1k_2, 2k_1k_2)$ 又被计算了一次。当计算 $k_3=k_1k_2$ 的倍数时，$(k_3, 2k_3)$ 被计算了第三遍。
根据 Lemma 1，我们可以知道，任何一个$k\in\mathbb{K}{even}$ 都可以被拆解成两个 $\mathbb{K}{odd}$ 中的元素。所以，我们在这里可以使用容斥原理：
\[Pairs = \sum_{k\in\mathbb{K}_{odd}}{\mathbf{C}_{\lfloor\frac{R}{k}\rfloor - \lfloor\frac{L-1}{k}\rfloor}^2} - \sum_{k\in\mathbb{K}_{even}}{\mathbf{C}_{\lfloor\frac{R}{k}\rfloor - \lfloor\frac{L-1}{k}\rfloor}^2}\]通过这种方法，我们可以保证算出来的 Pairs 一定没有重复的情况，那么有没有可能出现遗漏呢？
假设有$(x, y)$ 这样一对不互质的数对满足 $L\leq x, y\leq R$。那么它们的最大公因数$g$ 一定可以表示为以下形式：
\[g=\prod{p_i^{x_i}}\]所以 $x$ 与 $y$ 一定是 $k=\prod{p_i}$ 的倍数。
因此，$(x, y)$ 一定会被计算到而不会被遗漏。
删除 $MultPairs$？
在上一个部分，我们算出了所有满足以下条件的数组数量
\[\begin{aligned} L\leq x, y\leq R\\ gcd(x, y) \neq 1 \end{aligned}\]接下来，我们要从中剔除 $gcd(x, y) = x$ 的情况 （也就是 $y=mx$ 的情况）
如果 $y=mx$ 则 $x, y$ 一定不互质，所有这里直接计算出所有 $y=mx$ 的情况数量从上一部分的 Pairs 中减去即可。
对于每一个在 $[L, R]$ 区间内的值，使用以下公式我们都可以计算出它有多少个 pairs 是 $(x, mx)$ 形式的：
\[MultPair = \sum_{x=L}^R{{\lfloor\frac{R}{x}\rfloor} - 1}\]所以最后的结果如下:
\[\begin{aligned} Result &= \sum_{k\in\mathbb{K}_{odd}}{\mathbf{C}_{\lfloor\frac{R}{k}\rfloor - \lfloor\frac{L-1}{k}\rfloor}^2} - \sum_{k\in\mathbb{K}_{even}}{\mathbf{C}_{\lfloor\frac{R}{k}\rfloor - \lfloor\frac{L-1}{k}\rfloor}^2} - \sum_{x=L}^R{{\lfloor\frac{R}{x}\rfloor} - 1} \end{aligned}\]编程实现
L, R = map(int, input().split())
# Count all the non-prime pairs
g = [0] * (R + 1)
for d in range(R, 1, -1):
l = (L - 1) // d
r = R // d
g[d] = (r - l) ** 2
for e in range(2 * d, R + 1, d):
g[d] -= g[e]
print(g)
ans = 0
# Remove the (x, mx) case
for d in range(2, R + 1):
ans += g[d]
if L <= d <= R:
l = (L - 1) // d
r = R // d
ans -= 2 * (r - l) - 1
print(ans)
