求满足(a+b)可被K整除且a+b≤N的所有b值（暴力法超时求优化）

问题描述 #

给定三个正整数 (a, K, N)（满足 (0 < a, K, N < 10^9)），找出所有满足以下条件的正整数 (b)：

• (a + b \leq N)
• ((a + b) % K = 0)

示例：输入 10 6 40，输出结果为 2 8 14 20 26

暴力解法的问题 #

你提供的暴力解法通过遍历所有可能的 (b) 来判断是否符合条件，时间复杂度为 (O(N))。当 (N) 接近 (10^9) 时，遍历次数会达到上亿次，必然触发超时。

优化思路（数学推导） #

设 (s = a + b)，则问题可转化为寻找满足以下条件的 (s)：

1. (s) 是 (K) 的倍数（即 (s = m \times K)，(m) 为正整数）
2. (a < s \leq N)（因为 (b \geq 1)，所以 (s = a + b \geq a + 1)）

通过计算 (m) 的取值范围，直接推导所有符合条件的 (b)：

• 最小的 (m)（记为 (m_{\text{min}})）：取大于 (a/K) 的最小整数，即 (m_{\text{min}} = \lfloor a / K \rfloor + 1)
• 最大的 (m)（记为 (m_{\text{max}})）：取不超过 (N/K) 的最大整数，即 (m_{\text{max}} = \lfloor N / K \rfloor)

若 (m_{\text{min}} > m_{\text{max}})，说明没有符合条件的 (b)，输出 -1；否则，每个 (m) 对应的 (b = m \times K - a)，收集这些值即可。

优化后代码 #

a, K, N = map(int, input().split())
m_min = (a // K) + 1
m_max = N // K

if m_min > m_max:
    print(-1)
else:
    result = [str(m * K - a) for m in range(m_min, m_max + 1)]
    print(' '.join(result))

代码验证 #

以示例输入 10 6 40 为例：

• (a//K = 1)，故 (m_{\text{min}} = 2)
• (N//K = 6)，故 (m_{\text{max}} = 6)
• 遍历 (m=2) 到 (6)，计算得 (b) 分别为 (2, 8, 14, 20, 26)，与示例输出一致。

该方案的时间复杂度为 (O(M))（(M) 为符合条件的 (b) 的数量），远低于暴力解法的 (O(N))，即使 (N) 接近 (10^9) 也能高效运行。

内容的提问来源于stack exchange，提问作者Pson