题解：AT_abc414_e [ABC414E] Count A%B=C

HArcturus · 2025-07-13 13:55:59 · 题解

题目简述

给定正整数 N，统计满足以下条件的三元组 (a, b, c) 的个数：

1 \leq a, b, c \leq N
a \bmod b = c

输出方案数对 998244353 取模。

分析题目

对于每一组 (a, b)，c = a \bmod b 唯一确定。
但三元组需满足两两不同，且 c \in [1, N]。

所以完成以下三步

确定 b 的范围。
对于每一个 b，计算满足条件的 a 的取值个数。
枚举所有可能的 b，将每个 b 对应的合法 a 的取值个数累加，最后对答案取模后输出。

解题思路

确定 b 的范围

由于题目要求 a,b,c 两两不同，我们容易想到可以对 a,b 大小关系进行分类讨论：

a < b：a \bmod b = a，此时 c = a，不符“两两不同”，排除。
a > b：a \bmod b = c，此时 N \geq a > b > c \geq 0，三者必然不同。

因此，只需考虑 a > b 的情况，即 N \geq a > b > c \geq 0 的情况。

由 N \geq a > b > c \geq 0 与题目限制 c \geq 1，可得 b 的取值范围为 [2,N-1]。

计算满足条件的 a 的取值个数

由 N \geq a > b > c \geq 0 可得：对于每个 b，a 的取值范围为 [b+1, N]，共 N-b 个。

但还需满足 c = a \bmod b \geq 1，即 a 不是 b 的倍数（否则 c=0 不合法）。

在 a 的取值范围 [b+1, N] 内，a 是 b 的倍数的情况可以用等式表示：

a = k \times b ( k \in \mathbb{Z},\ 2 \leq k \leq \left\lfloor \frac{N}{b} \right\rfloor)

注释：因为 a > b 所以 k \neq 1。

从上诉等式可知，a 可以取的倍数个数为 k \in [2,\lfloor \frac{N}{b}\rfloor]。
即，a 是 b 的倍数的个数为 \left\lfloor \frac{N}{b} \right\rfloor - 1。

因此，对于每个 b，合法 a 的个数为：

(N-b) - (\left\lfloor \frac{N}{b} \right\rfloor - 1)

即

(N-b+1) - \left\lfloor \frac{N}{b} \right\rfloor

最终累加

综上所述，我们只需枚举 b 的所有可能取值 2 \leq b \leq N-1，对于每个 b，将其对应的合法 a 的个数 (N-b+1) - \left\lfloor \frac{N}{b} \right\rfloor 累加起来。

因此，答案可以表示为如下求和公式：

\sum_{b=2}^{N-1} \left[ (N-b+1) - \left\lfloor \frac{N}{b} \right\rfloor \right]

最后，将结果对 998244353 取模后输出即可。

代码实现

n = int(input())
mod = 998244353

ans = 0
for b in range(2, n):  # 2 <= b <= n-1
    ans += (n-b+1) - n//b
print(ans % mod)

复杂度分析

时间复杂度 O(N)，题目 N 范围 3 \leq N \leq 10^{12}，显然会超时。

优化：数论分块

分析求和公式

\begin{align*} &\sum_{b=2}^{N-1} \left[ (N-b+1) - \left\lfloor \frac{N}{b} \right\rfloor \right] \\ &= \underbrace{\sum_{b=2}^{N-1} (N-b+1)}_{\text{等差数列部分}} - \underbrace{\sum_{b=2}^{N-1} \left\lfloor \frac{N}{b} \right\rfloor}_{\text{整除分块部分}} \end{align*}

关键思路

等差数列部分

由于 b 从 2 到 N-1，(N-b+1) 形成一个首项为 N-1，末项为 2，共 N-2 项的等差数列。可以直接用等差数列求和公式计算：

\sum_{b=2}^{N-1} (N-b+1) = \frac{(N-2) \times (N+1)}{2}

整除分块部分

分块的核心思想

观察到 \left\lfloor \frac{N}{b} \right\rfloor 在 b 的某些连续区间内取值是相同的。我们可以按照 \left\lfloor \frac{N}{b} \right\rfloor 的值 k 对 b \in [2, N-1] 进行分块。对于每一个 k，计算对应区间内 b 的长度，然后将区间长度与该 k 的贡献相乘，累加到答案中。

如何找到每个分块的区间

设当前分块的起点为 left，此时 \left\lfloor \frac{N}{left} \right\rfloor = k。我们希望找到下一个分块的起点 L（L > left），使得 \left\lfloor \frac{N}{L} \right\rfloor < k，并且 L 尽可能小。
用数学式表示为：

L = \min \left\{\, x \mid x > left,\;\left\lfloor \frac{N}{x} \right\rfloor < k \,\right\}

进一步推导，\left\lfloor \frac{N}{L} \right\rfloor < k \implies N < k \times L \implies L > \frac{N}{k}，所以 L 取最小的满足 L > \frac{N}{k} 的整数，即

L = \left\lfloor \frac{N}{k} \right\rfloor + 1

最终，为了让分块区间尾不超过 N-1（即下一个分块区间头不超过 N），实际取 L = \min\left(\left\lfloor \frac{N}{k} \right\rfloor + 1,\, N\right)。

每个分块的贡献

在 b \in [left, L-1] 这个区间内，\left\lfloor \frac{N}{b} \right\rfloor 的值都等于 \left\lfloor \frac{N}{left} \right\rfloor，区间长度为 L - left，所以这一段的总贡献为 (L - left) \times \left\lfloor \frac{N}{left} \right\rfloor。

循环推进

每次处理完一个分块后，将 left 更新为 L，继续处理下一个分块。这个过程一直进行，直到分块的起点 left 超过 N-1，即循环条件为 left < N。

最终实现

n = int(input())
mod = 998244353

ans = 0

# 计算等差数列和部分：(n-b+1) 从 b=2 到 b=n-1
# 即首项为 n-1，末项为 2，共 n-2 项
ans += (n - 2) * (n + 1) // 2

# 分块计算 n//b 的和
# 分块区间在 [2, n-1]，注意边界处理
left = 2  # 当前分块区间的起点
while left < n:
    k = n // left  # 当前分块内 n//b 的值
    L = min(n // k + 1, n)  # 下一个分块区间的起点，当前分块区间的终点+1，不能超过 n
    ans -= (L - left) * k   # 区间长度*贡献
    left = L                # 移动到下一个分块的起点

print(ans % mod)