Problem : Count Multiples with Remainder / 统计余数为 K 的倍数

任务总览表

题目描述

给定三个正整数 A、B 和 K，请计算在区间 [1, B] 内，有多少个整数在除以 A 时余数等于 K。换句话说，统计满足 x mod A = K 的整数 x 的个数，其中 1 <= x <= B。

输入格式

输入包含三个正整数 A、B 和 K，保证 1 <= A, B <= 1000000，且 0 <= K < A。

输出格式

输出一个整数，表示在区间 [1, B] 内，除以 A 余数等于 K 的数的个数。

样例输入 1

3 10 1

样例输出 1

3

​解释​：在区间 [1, 10] 内，除以 3 余 1 的数有 1, 4, 7，共 3 个。

样例输入 2

4 20 2

样例输出 2

5

​解释​：在区间 [1, 20] 内，除以 4 余 2 的数有 2, 6, 10, 14, 18，共 5 个。

提示

• x mod A = K 表示 x 除以 A 的余数是 K。

• 满足 x mod A = K 的 x 可以表示为：

  x = K, K + A, K + 2A, ..., K + nA
  

  其中 K + nA <= B。

• 通过计算 (B - K) / A 可以得到满足条件的 x 的个数。

题目分析

​目标​：求区间 [1, B] 内，除以 A 余数等于 K 的整数个数。 ​思路​：

• x mod A = K 的数满足 x = K + n * A，其中 n 为非负整数。

• 最大的 x 不能超过 B，因此 K + n * A <= B。

• n 的最大值可以通过 (B - K) / A 计算，因此答案为：

  count = (B - K) / A + 1
  

  这可以在 O(1) 时间内计算得出。

时间复杂度分析

• 直接使用数学公式 (B - K) / A + 1 计算答案，时间复杂度为 O(1)。
• 由于 A, B 最大为 1000000，该解法能在 1 秒内高效运行。

结论

• 该问题可以用数学方法高效求解，无需遍历整个区间。
• 关键在于理解 x mod A = K 这一条件，并利用公式快速计算答案。